Алгоритм обчислення виразу за його ЗПЗ. Записи з варіантами

1. Алгоритм обчислення виразу за його ЗПЗ

Позначення операндів у ЗПЗ передують знакам операцій, які до них застосовуються, тому при читанні ЗПЗ спочатку обчислюються та запам'ятовуються операнди, а потім до них застосовується операція.

ЗПЗ виразу тепер читається, а для обчислень застосовується магазин. Але тепер це вже магазин операндів, а не знаків операцій. Числа, що є значеннями сталих чи змінних, переносяться в магазин. Якщо черговою лексемою є знак двомісної операції, то з магазина вилучаються два верхні елементи, і результат застосування операції до цих значень записується в магазин. За знаку одномісної операції з магазина вилучається лише один елемент. Ім'я функції на вході задає її застосування до елемента з верхівки магазина та вміщення результату в магазин. Після закінчення вхідного списку лексем у магазині зберігається лише одне число – значення всього виразу.

Процес обчислення можна подати послідовністю пар вигляду

(магазин операндів; непрочитана частина ЗПЗ).

Спочатку магазин порожній, а в кінці в ньому єдине значення.

Приклад 1. Обчислення ЗПЗ "2 3 * 4 +" подається так:

( ; 2 3 4 * - );

( 2 ; 3 4 * - ) – число 2 перенесено в магазин;

( 2 3 ; * 4 -) – те саме з 3;

( 6 ; 4 - ) – до операндів 2 і 3 застосовано множення;

( 6 4 ; - ) – число 4 перенесено в магазин;

(2 ; ) – до операндів 6 і 4 застосовано віднімання.

За обчислення ЗПЗ "2 3 4 * -" утвориться така послідовність:

( ; 2 3 4 * - );

(2 3 4 ; * -) – перенесено три числа в магазин;

(2 12 ; - ) – 3 і 4 перемножено;

(-10 ; ) – від 2 віднято 12. 

Уточнимо обробку ЗПЗ таким алгоритмом:

while на вході є лексема C do

case C of

стала чи ім'я змінної: заштовхнути її значення в магазин;

знак двомісної операції: виштовхнути з магазину два верхні елементи; обчислити результат застосування до них операції зі знаком С та заштовхнути результат в магазин;