Обратная польская (постфиксная) запись

5 6 7 8 9 10 11

Привычное определение арифметического выражения:

Арифметическая константа или инициализированная арифметическая переменная является арифметическим выражением.
Если А и В – арифметические выражения, то А#В и (А#В) – арифметические выражения.

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

((a+b*(c-e)/(d+f))/(a*b))/c

Арифметическое выражение в форме обратной польской записи (ПФ):

Арифметическая константа или инициализированная арифметическая переменная является арифметическим выражением ПФ.
Если А и В – арифметические выражения ПФ, то АВ # – арифметическое выражение ПФ.

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

a b c e - * d f + / + a b * / c /

Как получить обратную польскую запись?

Рекурсивное решение: Если арифметическое выражение является арифметической константой или инициализированной арифметической переменной, то по определению это и есть арифметическое выражение ПФ. Если арифметическое выражение имеет вид А#В или (А#В), то нужно записать ПФ для А, далее приписать ПФ для В, а затем записать знак операции #.

((a+b*(c-e)/(d+f))/(a*b))/c

(((a+((b*(c-e))/(d+f)))/(a*b))/c)

((a+((b*(c-e))/(d+f)))/(a*b))c/

(a+((b*(c-e))/(d+f)))(a*b)/c/

a((b*(c-e))/(d+f))+ab*/c/

a(b*(c-e))(d+f)/+ab*/c/

ab(c-e)*df+/+ab*/c/

abce-*df+/+ab*/c/

Задача.

Вычислить значение арифметического выражения, записанного в виде обратной польской записи.

Решение.

Создаем пустой стек. Читаем арифметическое выражение ПФ слева направо. Если встречается константа или имя инициализированной переменной, то в стек вталкивается соответствующее значение. Если встречается знак арифметической операции, то из стека выбираются два значения, над ними выполняется операция (первое значение – правый операнд, второе значение – левый операнд), результат операции вталкивается в стек.

Докажите, что в результате такой обработки правильного выражения ПФ в вершине стека будет лежать значение арифметического выражения, других записей в стеке не будет.

Пусть a=1, b=2, c=3, d=4, e=5, f=6, тогда алгоритм вычисления выражения

a b c e - * d f + / + a b * / c / реализуется так:

Номер действия	Содержание стека	Обратная польская запись
		1,2,3,5,-,,4,6,+,/,+,1,2,,/,3,/
		2,3,5,-,,4,6,+,/,+,1,2,,/,3,/
	1,2	3,5,-,,4,6,+,/,+,1,2,,/,3,/
	1,2,3	5,-,,4,6,+,/,+,1,2,,/,3,/
	1,2,3,5	-,,4,6,+,/,+,1,2,,/,3,/
	1,2,-2	,4,6,+,/,+,1,2,,/,3,/
	1,-4	4,6,+,/,+,1,2,*,/,3,/
	1,-4,4	6,+,/,+,1,2,*,/,3,/
	1,-4,4,6	+,/,+,1,2,*,/,3,/
	1,-4,10	/,+,1,2,*,/,3,/
	1,-0.4	+,1,2,*,/,3,/
	0.6	1,2,*,/,3,/
	0.6,1	2,*,/,3,/
	0.6,1,2	*,/,3,/
	0.6,2	/,3,/
	0.3	3,/
	0.3,3	/
	0.1