Зворотний польський запис та алгоритм його побудови, Детальна інформація

\x00F0

o

o

oe

Nоли у вхідній послідовності читається знак операції op2, з верхівки магазина треба видати у вихідний вираз усі знаки, пріоритети яких не нижчі від пріоритету op2 (усі вони є знаками з виразу E1), і тільки після цього запам'ятати op2 у магазині. Якщо пріоритет знака з верхівки магазина нижче ніж у op2, то op2 записується в магазин, оскільки має появитися у вихідному виразі раніше.

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

(вихідна послідовність лексем;

магазин;

непрочитана частина виразу).

Верхівку магазина будемо вказувати праворуч.

Приклад 1. Початок перетворення виразу a+b*c зображається послідовністю трійок

( ; ; a + b * c ) – початковий стан: вихідна послідовність і магазин порожні;

( a ; ; + b * c ) – ім'я перенесено у вихідну послідовність;

( a ; + ; b * c ) – знак перенесено в магазин;

( a b ; + ; * c ) – ім'я перенесено у вихідну послідовність.

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

( a b ; + * ; c ).

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

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

( a b ; + ; - c ),

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

( a b + ; - ; c ).

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

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

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

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

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

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

case C of

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