Алгоритм вычисления выражения в польской форме записи

1. Просматриваем префиксное (постфиксное) запись справа налево (слева направо)

2. Если встречаем операнд, то помещаем его в стек

3. Если встречаем знак операции,

то выполняем эту операцию, используя в качестве операндов два числа с вершины стека.

Результат помещаем в стек.

4. Если польская запись не закончена, то переходим к 1., иначе к 5.

5. Результат вычисления извлекаем из стека

Примеры

Префиксная форма записи	Инфиксная форма записи	Постфиксная форма записи
	(1)
+ 1 2	1 + 2	1 2 +
+ 1 2	(1 + 2)	1 2 +
+ – 1 2 3	1 – 2 + 3	1 2 – 3 +
* 2 + 3 4	2 * (3 + 4)	2 3 4 + *
– + 1 / * 2 3 4 5	1 + (2 * 3) / 4 – 5	1 2 3 * 4 / + 5 –

Реализация на Паскале

Постфиксное выражение

{Перевод}

Var stek: array [1..100] of char;

Procedure push(c:char);

Begin

m:=m+1;

stek[m]:=c;

End;

Procedure pop (var c:char);

Begin

c:=stek[m];

m:=m-1;

End;

Procedure inf_to_post(s:string);

{Вычисление}

Uses crt;

Var stek: array [1..100] of real;

Procedure push(c:real);

Procedure pop (var c:real);

Function calc_post(s:string):real;

Var

i,code:integer;

Begin

m:=length(s);

n:=m;

for i:=1 to n do

case s[i] of

'0'..'9': begin

val(s[i],x,code);

push(x);

end;

'+': begin

pop(x); pop(y);

res:=x+y;

push(res);

end;

'-': begin

pop(x); pop(y);

res:=x-y;

push(res);

end;

'*': begin

pop(x); pop(y);

res:=x*y;

push(res);

end;

'/': begin

pop(x); pop(y);

res:=x/y;

push(res);

end;

end;

pop(res);

calc_post:=res;

End;

Дата добавления: 2015-07-10