Польская инверсная запись (ПОЛИЗ)

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

в обратной польской записи буде выглядеть следующим образом:

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

Входная строка	Стек	Пояснение
4 A * 2 X / - 3 B * 2 Y * + *
4 A * 2 X / - 3 B * 2 Y * + *	A4
4 A * 2 X / - 3 B * 2 Y * + *	R₀	R₀=4*A
4 A * 2 X / - 3 B * 2 Y * + *	2R₀
4 A * 2 X / - 3 B * 2 Y * + *	X2R₀
4 A * 2 X / - 3 B * 2 Y * + *	R₁R₀	R₁=2/X
4 A * 2 X / - 3 B * 2 Y * + *	R₀	R₀=R₀-R₁
4 A * 2 X / - 3 B * 2 Y * + *	3R₀
4 A * 2 X / - 3 B * 2 Y * + *	B3R₀
4 A * 2 X / - 3 B * 2 Y * + *	R₁R₀	R=3*B
4 A * 2 X / - 3 B * 2 Y * + *	2R₁R₀
4 A * 2 X / - 3 B * 2 Y * + *	Y2R₁R₀
4 A * 2 X / - 3 B * 2 Y * + *	R₂R₁R₀	R₂₌2*Y
4 A * 2 X / - 3 B * 2 Y * + *	R₁R₀	R₂=R₁+R₂
4 A * 2 X / - 3 B * 2 Y * + *	R₀	R₀=R₀*R₁

Таблица 2. Вычисление значения выражения, заданного польской записью.

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

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

Операнды сразу помещаются в выходную строку.

Знаки операций сначала помещаются в стек. Прежде чем быть помещенным в стек, знак операции выталкивает из стека все операции, которые имеют приоритет больше или равный приоритета входной операции.

Открывающая скобка просто помещается в стек как операция с самим низким приоритетом.

Закрывающая скобка выталкивает из стека в выходную строку все операции вплоть до ближайшей открывающей скобки, которая удаляется из стека, но в выходную строку не помещается. Закрывающая скобка в стек не помещается.

После того как входная строка закончилась, остаток стека выталкивается в выходную строку.

Текст алгоритма преобразования приведен ниже.

struct opri{ // знаки операций и их приоритеты