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