Вычисление значения арифметического выражения

Функция «Голова(р)» с побочным эффектом (р указывает на непустой неатомарный линейный список).

Голова:=р^.уров;

p^.уров:=Голова^.след;

Голова^.след:=nil

{Серия картинок, иллюстрирующих работу функции Голова}

"Правильное" арифметическое выражение представлено как "правильный" линейный список. Атомы a,b,c,... – инициализированные переменные или константы, атомы + - * / – бинарные операции.

Функция VAL(p:pElem) возвращает значение арифметического выражения, заданного указателем p.

VAL(p:pElem)

Список пуст?
	Список атом?
	VAL=p^.атом	x=VAL(Голова(p))
		оп=Голова(p)^.атом
		y=VAL(p)
		если оп=+ VAL=x+y
		если оп=- VAL=x-y
		если оп=* VAL=x*y
		если оп=/ VAL=x/y

Разъяснения:

Вот «правильный» линейный список

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) Построить алгоритм обхода элементов линейного списка (восстановить строку символов с учетом вложенности).