5. Обратная польская строка, как промежуточная форма программы

5.1. Обратная польская строка для арифметических выражений

Обратная польская строка (ОПС) является бесскобочной записью арифметических выражений. В отличии от обычной (инфиксной) записи, когда знак двуместной операции записывается между операндами, участвующими в операции, в ОПС вначале пишутся операнды, а затем – знак операции. При этом операнды могут быть простыми (переменными, константами), или сложными, т.е. результатами других операций. В табл. 10 приведены примеры формул в обычной записи и в виде ОПС.

Табл. 10

№	Формула	ОПС
1	a + b	a b +
2	a*(c + d)	a c d + *
3	(x + y)*(a*x – b*y)	x y + a x * b y * – *

Если в обычной записи формул необходимо учитывать приоритеты операций, то порядок исполнения действий в ОПС полностью определяется местоположением в ней знаков операций. Следует учесть, что при переходе от формулы к ОПС порядок простых операндов не изменяется.

В записи ОПС могут использоваться операции с различным числом операндов: с одним, двумя, тремя и т.д., и даже без операндов. При этом количество операндов определяется знаком операции. Поэтому, в частности, операция «унарный минус» и «бинарный минус» должны обозначаться различающимися знаками.

Вычисление по заданной ОПС можно выполнить интерпретатором, использующим магазин. В магазине сохраняются значения операндов и результаты вычислений. Принцип работы интерпретатора следующий. ОПС просматривается слева направо. Если очередной элемент в ОПС – операнд, то его значение записывается в магазин. Если очередной элемент в ОПС – операция, то из магазина считываются операнды для этой операции, после чего операция выполняется, а ее результат записывается в магазин. Если ОПС корректная, то после всех действий в магазине будет записано единственное значение – результат вычислений.

Пример 9. Дана формула a*(c + d). В табл. 11 приведены шаги алгоритма вычисления ОПС.

Табл. 11

№ шага	Входные символы	Содержимое магазина
1	a c d + *
2	c d + *	a
3	d + *	a	c
4	+ *	a	c	d
5	*	a	c+d
6		a*(c+d)

Конец примера.

Пример 10. Дана формула (x + y)*(a*x – b*y). В табл. 11 приведены шаги алгоритма вычисления ОПС.

Табл. 12

№ шага	Входные символы	Содержимое магазина
1	x y + a x * b y * – *
2	y + a x * b y * – *	x
3	+ a x * b y * – *	x	y
4	a x * b y * – *	x+y
5	x * b y * – *	x+y		a
6	* b y * – *	x+y		a	x
7	b y * – *	x+y		a*x
8	y * – *	x+y		a*x		b
9	* – *	x+y		a*x		b	y
10	– *	x+y		a*x		b*y
11	*	x+y		a*x– b*y
12		(x+y)*(a*x–b*y)

Конец примера.