Зворотний польський запис та алгоритм його побудови

На порядок знаків у вихідному виразі впливає їх старшинство, або пріоритет:

L( a + b * c ) = a b c * + ; L( a + b - c ) = a b + c - .

Операція '*' старша за '+', тому в першому виразі операція '+' застосовується до значень a та b*c. У другому виразі старшинство '+' та '-' однакове, операції мають властивість лівостороннього зв'язування, тому '+' застосовується до a і b, а '-' – до a+b і c.

Отже, коли у вхідній послідовності читається знак операції 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 пов'язується з операцією '+' ліворуч.

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