Після цього знак '*' вміщується в магазин над знаком '+':

( a b ; + * ; c ).

Пріоритет операції '*' вищий від '+', тому b є операндом '*', а не '+'.

При перетворенні виразу a+b-c результатом читання його початку a+b буде

( a b ; + ; - c ),

після чого знак '-' "виштовхне" з магазина '+', тобто наступною буде трійка

( a b + ; - ; c ).

Пріоритети '+' і '-' рівні, тому b пов'язується з операцією '+' ліворуч.?

Відкриваюча та відповідна їй закриваюча дужки задають початок і кінець виразу, всі знаки операцій якого мають з’явитися у вихідному виразі раніше від знаків, що є в магазині перед появою відкриваючої дужки. Для відокремлення цих знаків відкриваюча дужка записується в магазин. За появи на вході закриваючої дужки всі знаки операцій до відкриваючої дужки виштовхуються з магазина у вихідний вираз, а дужка вилучається з магазина, тобто дужки "взаємно знищуються".

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

Після того, як вираз прочитано, в магазині ще можуть залишитися знаки операцій; їх треба записати у вихідну послідовність.

Отже, уся описана обробка лексем подається таким алгоритмом:

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

case C of

стала чи ім'я змінної: скопіювати її у вихідну послідовність;

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

відкриваюча дужка: заштовхнути С в магазин;

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

end;

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

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

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

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

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

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

Приклад 20.2. Обчислення ЗПЗ "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

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

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

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

end;

видати верхній елемент магазина як результат.

Задачі

20.2.* Імітувати процес обчислення ЗПЗ:

а) 1 2 3 4 + - *; б) 1 2 3 + 4 - *; в) 1 2 + 3 - 4 *.

20.3. У процесі побудови ЗПЗ, якщо знак операції потрапляє до вихідної послідовності, то її операнди уже перебувають там, і операцію можна застосувати до них. Поміняти алгоритм побудови ЗПЗ так, щоб замість побудови одразу обчислювалося значення початкового виразу. Можна використати два магазини – знаків операцій та операндів.

4. Записи з варіантами.

У підрозділах 20.5, 20.6 ми уточнимо у вигляді підпрограм наведені вище алгоритми побудови ЗПЗ та обчислення значення виразу. Там ми скористаємося зручним засобом мови Паскаль, який досі не розглядався, – це записи з варіантами.

У нашій задачі ЗПЗ виразу будується у вигляді послідовності лексем. Послідовність можна подати масивом, списком, або файлом. У будь-якому разі це буде послідовність однотипних елементів. Проте у виразах є лексеми чотирьох різновидів: сталі, імена, знаки операцій і дужки. Природно у ЗПЗ зберігати не сталі чи імена змінних, а їх значення. Знаки операцій та дужки є символами, а імена функцій – рядками. Отже, доводиться говорити про кілька різних типів для подання лексем. Але незрозуміло, як різнотипні елементи зібрати в одну послідовність.

Одним із розв'язань цієї суперечності є використання записів із варіантами. Подивимося на лексеми як на пари вигляду (різновид, значення). Наприклад, стала 12 подається як (стала,