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

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

Например, необходимо вычислить 7+5*2 : 752*+

Вход	Действия	Магазин (стек)
752*+	Записать в стек операнд (7)	7
52*+	Записать в стек операнд (5)	57
2*+	Записать в стек операнд (2)	257
*+	1. прочитать операнд (2) 2. прочитать операнд (5) 3. выполнить операцию (*) 4. записать результат в стек (10)	10 7
+	1. прочитать из магазина (10) 2. прочитать из магазина (7) 3. выполнить операцию (+) 4. записать результат	17

Алгоритм Э.Дейкстры перевода выражения в ПОЛИЗ (метод стека с приоритетами):

1. Каждому знаку операции присваивается числовой приоритет. Он начинается с цифры 2 и операции, выполняемой в первую очередь, имеют больший приоритет.

2. Открывающимся скобкам присваивается 0, закрывающимся 1.

3. Входная строка читается слева направо. Операнды по мере считывания помещаются в выходную строку.

4. Знаки перед записью в выходную строку помещаются в стек по следующему алгоритму:

a) открывающаяся скобка (знак с приоритетом 0) помещается в стек

b) если приоритет знака операции больше приоритета знака на вершине стека или стек пуст, новый знак добавляется в стек

c) если приоритет знака меньше или равен приоритету знака на вершине стека, из стека в выходную строку “выталкиваются” все знаки с приоритетами, большими или равными приоритету входного знака. После этого входной знак записывается в стек

d) закрывающаяся скобка выталкивается в выходную строку все знаки до открывающейся скобки. Открывающаяся скобка удаляется из стека, а закрывающаяся туда не записывается.

5. после просмотра всех символов входной строки из стека выталкиваются оставшиеся знаки.

Например:

стек	Выходная строка
(	a
+(	ab
	ab+
/	ab+
(/	ab+c
+(/	ab+cd
/	ab+cd+
	ab+cd+/