Обратная польская запись: как вычислять со стеком

Обратная польская запись - способ записать выражение так, чтобы знак операции следовал за её аргументами. Вместо привычного получаем . Скобки здесь не нужны: последовательность символов уже задаёт порядок действий. Чтобы вычислить результат, достаточно идти слева направо и хранить промежуточные значения в стеке. Выберите выражение в интерактивном примере и проследите, как меняется число значений в стеке после каждого шага.
Что означает запись после операндов
В обычной, инфиксной, форме знак стоит между операндами: . В постфиксной сначала записывают оба операнда, затем операцию: . Обратную польскую запись часто сокращают до ОПЗ или RPN. Для сравнения, в прямой польской, или префиксной, форме операция предшествует аргументам: .
Объект обработки - токен, то есть отдельное число, имя переменной или знак операции. Пробелы помогают отделить многозначные числа друг от друга: означает сумму двенадцати и трёх, а не последовательность отдельных цифр. У каждой операции должно быть известно число аргументов: сложение здесь бинарное, оно принимает два значения. Это условие важно для однозначного чтения.
Как вычислить выражение с помощью стека
Стек работает по принципу «последним пришёл - первым вышел». Представьте стопку карточек: положить новую карточку и взять существующую можно с вершины. Это отличается от очереди в обходе графа в ширину, где первым извлекают элемент, добавленный раньше остальных.
Алгоритм обработки бинарных операций состоит из четырёх шагов:
- Прочитайте следующий токен слева направо. Число положите на вершину стека.
- Встретив знак, снимите два значения: сначала правый операнд, затем левый.
- Примените операцию в порядке «левый знак правый» и положите результат обратно.
- После последнего токена проверьте, что в стеке осталось ровно одно значение.
Например, в сначала снимаем , затем и вычисляем . При сложении ошибка порядка могла бы остаться незамеченной, но для вычитания и деления она меняет ответ. Именно такой проход со стеком описан в учебных материалах Принстонского университета.
Пример: от выражения к результату
Пусть исходное выражение - . Скобки указывают выполнить вычитание раньше умножения. В ОПЗ результат записывается как . В таблице стек указан снизу вверх: последнее число в строке находится на вершине.
| Токен | Действие | Стек после шага |
|---|---|---|
| Положить число | ||
| Положить число | ||
| Вычислить | ||
| Положить число | ||
| Вычислить |
Максимальная глубина стека в этом примере равна двум, а конечное значение - десяти. Высота столбцов в интерактиве показывает именно число сохранённых значений, а не их сумму. Поставьте ползунок на третий шаг: на вершине будет , потому что два предыдущих числа уже заменены результатом вычитания.

Для сравнения, соответствует . На третьем шаге в стеке уже три числа, а умножение выполняется раньше сложения. Одинаковые числа и знаки в другом порядке задают другое дерево вычисления.
Как перевести обычное выражение в ОПЗ
Удобно начинать перевод с самых внутренних подвыражений. Для каждой операции сначала запишите её левый аргумент, затем правый, а после них сам знак. Если аргумент - ещё одно выражение, примените к нему то же правило. Это похоже на сборку логической схемы по выражению: результат внутреннего действия становится входом внешнего.
Рассмотрим . Левая часть превращается в , правая - в ; знак умножения ставим после обеих частей. Итого . Переменные остаются операндами: чтобы получить число, нужно подставить их значения или хранить соответствующие значения в стеке.
Для длинной записи применяют алгоритм сортировочной станции: операнды сразу отправляют в выходную последовательность, а операции временно хранят в отдельном стеке. При встрече нового знака из стека снимают знаки с более высоким приоритетом, а при одинаковом приоритете учитывают ассоциативность. Скобки ограничивают группу: закрывающая скобка вызывает выгрузку до соответствующей открывающей. В конце оставшиеся операции переносят в выход; несогласованные скобки указывают на ошибку. Это стек операций при переводе, а не стек значений при последующем вычислении.
При ручном переводе можно проверить результат обратным способом: вместо чисел помещать в стек текстовые фрагменты в скобках. Встретив знак, снимите два фрагмента и объедините их, сохранив левый и правый порядок. Для последовательно получаются фрагменты и , а затем их произведение. Такая проверка показывает структуру даже тогда, когда значения переменных ещё неизвестны.
Полезно различать форму записи и сам алгоритм её обработки. Одно и то же дерево вычисления можно представить обычной формулой со скобками или последовательностью ОПЗ. Замена формы не меняет математический смысл выражения при одинаковых правилах операций, но делает порядок выполнения явным. При реализации проверяйте токены ещё до вычисления: неизвестное имя или символ не должны незаметно превращаться в число.
Приоритет, ассоциативность и порядок аргументов
В инфиксной записи приоритеты и скобки помогают построить порядок действий. Например, означает , поэтому переводится в . Но превращается в . После перевода приоритеты при вычислении ОПЗ больше не нужны: операции выполняются по мере появления.
При равном приоритете важна ассоциативность. Вычитание обычно левоассоциативно: читается как и записывается . Если исходное выражение имеет вид , получится ; результат уже другой. Для каждой новой операции, в том числе возведения в степень или унарного минуса, нужно заранее определить её арность и правила перевода. Отрицательное число как отдельный токен также надо отличать от бинарного знака вычитания.
Проверка корректности и сложность
Для выражения только из чисел и бинарных операций можно проверять глубину стека без вычисления самих значений. Число увеличивает глубину на один; операция требует хотя бы двух значений и уменьшает глубину на один. В конце глубина должна равняться единице. Это проверка структуры: она не выявит, например, деление на ноль.
Запись не проходит проверку: после сложения осталось только одно число, поэтому для умножения не хватает второго. А оставляет два значения после чтения и тоже не задаёт единственный результат. Для корректного выражения из токенов один проход занимает операций, если считать действия со стеком и арифметику постоянными по стоимости. Стек в худшем случае хранит значений. Для очень больших чисел стоимость арифметики зависит от их длины; это важно, например, при умножении длинных чисел алгоритмом Карацубы.
Проверка глубины позволяет быстро найти место структурной ошибки. Начинайте с нуля и отмечайте новое значение после каждого токена. Как только операция требует больше элементов, чем есть сейчас, продолжать разбор уже бессмысленно: никакие последующие числа не станут её недостающими левыми аргументами. Если такого сбоя нет, но в конце осталось несколько значений, выражение, возможно, состоит из нескольких незавершённых частей. Исправление зависит от исходной задачи: автоматически добавлять операцию было бы догадкой.
Оценка памяти относится к максимальной глубине за весь проход, а не только к итоговому стеку. Например, у корректного выражения в конце остаётся одно значение, хотя ранее их могло быть много. Последовательность из нескольких чисел перед первыми знаками особенно наглядно показывает, откуда возникает потребность в памяти.
Где применяется и какие есть ограничения
Постфиксная форма удобна при разборе выражений, в учебных стековых машинах и калькуляторах: операция выполняется, когда её аргументы уже доступны. В руководстве HP описан режим RPN, где числа вводятся перед операцией. Конкретный калькулятор может иметь ограниченное число регистров и собственные правила ввода, поэтому его поведение не следует автоматически переносить на абстрактный стек неограниченного размера.
ОПЗ не устраняет возможные ошибки самих вычислений: деление на ноль, переполнение и округление зависят от используемой числовой модели. Например, при работе с целыми числами фиксированной разрядности имеет значение способ их хранения; отдельно разобрано представление отрицательных чисел в дополнительном коде. Запись определяет порядок операций, но не гарантирует бесконечную точность.
Частые ошибки
- Менять местами снятые значения. Первым снимается правый операнд: равно , а не .
- Применять инфиксный приоритет повторно. В вычитание уже стоит раньше умножения.
- Не отделять токены. Без разделителей многозначные числа могут читаться неоднозначно.
- Не проверять финальный стек. Недостаток операндов и лишние значения делают запись некорректной.
- Считать любой минус одинаковым. Унарная операция и бинарное вычитание требуют разных правил разбора.
FAQ
Почему запись называется обратной польской?
В польской записи операция предшествует операндам, а в обратной следует за ними. Название связано с польской нотацией логика Яна Лукасевича; в практике встречаются также названия «постфиксная запись» и RPN.
Нужны ли в ОПЗ скобки?
Для корректно заданных операций с известным числом аргументов скобки не нужны: структура определяется порядком токенов и арностью операций. Разделители между токенами при этом могут быть необходимы.
Можно ли записывать функции?
Да. Например, если обозначить унарную функцию отдельным токеном, означает синус . Для функции с переменным числом аргументов число аргументов нужно сообщить отдельно или определить форматом записи.
Коротко
Обратная польская запись помещает операцию после её аргументов. Для вычисления числа последовательно кладут в стек, а каждый знак заменяет нужное число операндов результатом. Порядок снятия особенно важен для вычитания и деления; корректное бинарное выражение заканчивается одним значением в стеке.
Читайте также

Стек на списке: реализация push и pop через массив
Как реализовать стек на списке: индекс вершины, амортизированная сложность push O(1), расширение массива вдвое при переполнении и почему pop не освобождает память сразу.

Алгоритм LZ77: сжатие с помощью ссылок назад
Алгоритм LZ77 на пошаговом примере: как скользящее окно находит повторы, что означают расстояние и длина, как работает перекрытие и от чего зависит размер результата.

Алгоритм LZW: сжатие данных с помощью словаря
Алгоритм LZW по шагам: как строится словарь фраз, выдаются коды и восстанавливается исходная строка. Разберём пример, особый случай декодирования и оценку размера.

Блок-схема алгоритма: условный оператор
Как построить блок-схему алгоритма с условным оператором: обозначения, полное и неполное ветвление, пример проверки чётности и трассировка двух путей.

Числа Белла: разбиения множества и формула
Числа Белла считают разбиения множества на непустые группы. Разбираем подробные примеры, рекуррентную формулу, связь с числами Стирлинга и алгоритм вычисления.

Числа трибоначчи: формула и примеры вычисления
Числа трибоначчи: три начальных значения, рекуррентная формула и расчёт по шагам. Как последовательность считает пути по ступенькам и как написать эффективный алгоритм.