Вычисление значения арифметического выраженияФункция «Голова(р)» с побочным эффектом (р указывает на непустой неатомарный линейный список). Голова:=р^.уров; p^.уров:=Голова^.след; Голова^.след:=nil {Серия картинок, иллюстрирующих работу функции Голова} "Правильное" арифметическое выражение представлено как "правильный" линейный список. Атомы a,b,c,... – инициализированные переменные или константы, атомы + - * / – бинарные операции. Функция VAL(p:pElem) возвращает значение арифметического выражения, заданного указателем p. VAL(p:pElem)
Разъяснения: Вот «правильный» линейный список x=VAL(Голова(p)). Вот результат применения функции Голова: оп=Голова(p)^.атом. Вот результат второго применения функции Голова: y=VAL(p). Вот результат третьего применения функции Голова: Вопросы: 1) В какой последовательности будут выполняться операции одного уровня? 2) Почему рекурсия обязательно завершится? Задача Имеется правильное выражение в виде строки. Построить линейный список для этого выражения. pElem=^Elem; Elem=record след:pElem; case R:0..1 of 0: (уров:pElem); 1: (атом:T) end; Выражение вводится с клавиатуры. procedure LS (var p:pElem); var c:char; begin if not eoln begin read(c); case c of ‘(‘: begin new(p); p^.R:=0; LS(p^.уров); LS(p^.след); end; ‘a’..’z’,’+’,’-‘,’*’,’/’: begin new(p); p^.R:=1; p^.атом:=с; LS(p^.след); end; ‘)’: p:=nil; end; end else p:=nil; end;
Задачи 1) Написать алгоритм вычисления значения арифметического выражения, используя операцию "расчленение". 2) Имеется линейный список для "правильного" арифметического выражения. Построить линейный список для обратной польской записи этого выражения. 3) Построить алгоритм обхода элементов линейного списка (восстановить строку символов с учетом вложенности).
|