Обратная польская запись

Обратная польская запись (ОПЗ, также известная как постфиксная нотация, бесскобочная запись) — это форма записи математических выражений и логических формул, в которой оператор располагается после своих операндов. В отличие от традиционной инфиксной записи (например, «2 + 2»), где оператор находится между операндами, в ОПЗ выражение «2 2 +» означает то же самое. Основным преимуществом такой нотации является отсутствие необходимости в скобках для указания приоритета операций и в правилах ассоциативности, что упрощает алгоритмическое вычисление выражений, особенно в стековых вычислительных машинах и языках программирования.

История

Идея бесскобочной записи математических выражений была впервые предложена польским логиком и математиком Яном Лукасевичем в 1920-х годах. Изначально он разработал префиксную нотацию (польскую запись), где оператор ставится перед операндами (например, «+ 2 2»). Обратная польская запись, где оператор следует за операндами, является её зеркальным отражением.

В 1950-х и 1960-х годах, с развитием компьютерных наук и появлением первых компиляторов, возникла потребность в эффективных методах вычисления арифметических выражений. Австралийский учёный Чарльз Хэмблин в 1957 году независимо описал постфиксную нотацию и её применение в стековых вычислениях. Он же ввёл термин «обратная польская запись». В 1960 году Хэмблин реализовал эту идею в аппаратном обеспечении, создав один из первых стековых калькуляторов.

Значительный вклад в популяризацию ОПЗ внесла компания Hewlett-Packard (HP). Начиная с 1968 года, HP выпустила серию настольных калькуляторов (например, HP 9100A), а затем и инженерных калькуляторов (HP-35, 1972 год), которые использовали обратную польскую запись. Это сделало ОПЗ стандартом для профессиональных инженерных расчётов на десятилетия.

Принцип работы и алгоритм вычисления

Вычисление выражения в обратной польской записи выполняется с использованием структуры данных «стек» (LIFO — Last In, First Out). Алгоритм является линейным и не требует рекурсивных вызовов или анализа приоритетов.

Алгоритм вычисления (постфиксный калькулятор)

1. Выражение считывается слева направо.
2. Если текущий элемент — операнд (число или переменная), он помещается (push) в стек.
3. Если текущий элемент — оператор (например, +, -, *, /):

• Из стека извлекаются (pop) два верхних операнда. Первый извлечённый операнд считается правым, второй — левым.
• Выполняется соответствующая операция над этими операндами.
• Результат операции помещается обратно в стек.

1. После обработки всего выражения в стеке остаётся ровно одно значение — результат.

Пример

Рассмотрим выражение (3 + 4) 5. В инфиксной записи оно требует скобок. В обратной польской записи оно выглядит как 3 4 + 5 .

Пошаговое вычисление:

1. Считываем 3 — помещаем в стек. Стек: [3].
2. Считываем 4 — помещаем в стек. Стек: [3, 4].
3. Считываем + — извлекаем 4 (правое) и 3 (левое). Вычисляем 3 + 4 = 7. Помещаем 7 в стек. Стек: [7].
4. Считываем 5 — помещаем в стек. Стек: [7, 5].
5. Считываем — извлекаем 5 (правое) и 7 (левое). Вычисляем 7 5 = 35. Помещаем 35 в стек. Стек: [35].
6. Конец выражения. Результат: 35.

Преобразование из инфиксной записи

Для перевода выражения из стандартной инфиксной записи в обратную польскую используется алгоритм, известный как «сортировочная станция» (Shunting yard algorithm), также разработанный Эдсгером Дейкстрой. Этот алгоритм использует два стека: один для операторов, другой для вывода результата. Он обрабатывает операнды, операторы, скобки и функции, учитывая их приоритет и ассоциативность.

Преимущества и недостатки

Преимущества

• Отсутствие скобок: Приоритет операций задаётся исключительно порядком следования операндов и операторов, что исключает неоднозначность и упрощает синтаксический анализ.
• Простота вычисления: Алгоритм вычисления является линейным и не требует рекурсии, что делает его быстрым и эффективным для реализации в программном и аппаратном обеспечении.
• Минимальное использование памяти: Для вычисления требуется только стек, что позволяет реализовать калькулятор с минимальным объёмом оперативной памяти.
• Удобство для ввода с клавиатуры: При использовании ОПЗ на калькуляторе пользователю не нужно нажимать клавишу «равно» после каждого действия — результат промежуточных вычислений всегда виден на стеке. Это ускоряет цепочки вычислений.

Недостатки

• Неинтуитивность для человека: Для людей, привыкших к инфиксной записи, чтение и запись длинных выражений в ОПЗ может быть непривычным и требовать определённой тренировки. Например, выражение (a + b) (c - d) / e в ОПЗ превращается в a b + c d - e /.
• Сложность отладки: Ошибки в последовательности операторов и операндов могут привести к неверным результатам, а визуально отследить логику сложного выражения сложнее, чем в инфиксной записи.

Применение

Калькуляторы и вычислительная техника

Обратная польская запись наиболее известна благодаря её использованию в инженерных и финансовых калькуляторах Hewlett-Packard. Многие программисты и инженеры предпочитают калькуляторы с ОПЗ за скорость и точность ввода. Также ОПЗ используется в некоторых программных калькуляторах и эмуляторах.

Языки программирования

ОПЗ является основой для стековых языков программирования, таких как Forth, PostScript и языка ассемблера виртуальной машины Java (JVM). В этих языках программа представляет собой последовательность команд, которые манипулируют стеком данных. Например, в языке Forth код для вычисления (3 + 4) 5 будет выглядеть как 3 4 + 5 . (точка выводит результат на экран).

Компиляторы и интерпретаторы

Многие компиляторы и интерпретаторы языков программирования (например, C, Pascal, Python) на этапе синтаксического анализа преобразуют инфиксные выражения в обратную польскую запись или её эквивалент (например, трёхадресный код) для последующей генерации машинного кода или выполнения на виртуальной машине. Это упрощает процесс генерации кода и оптимизации.

Теория автоматов и формальных языков

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

Интересные факты

• В 1970-х годах компания Texas Instruments, основной конкурент Hewlett-Packard на рынке калькуляторов, использовала традиционную инфиксную запись с клавишей «равно». Это привело к так называемым «калькуляторным войнам», где сторонники ОПЗ и инфиксной записи отстаивали преимущества своих устройств.
• Алгоритм «сортировочная станция» Дейкстры, используемый для преобразования в ОПЗ, назван так по аналогии с железнодорожной сортировочной станцией, где вагоны (операнды) и локомотивы (операторы) переставляются в нужном порядке.
• В некоторых языках программирования, таких как RPL (на калькуляторах HP серии 48/49/50), используется модифицированная версия ОПЗ, поддерживающая работу с объектами, списками и символами, а не только с числами.

Источники

• Лукасевич, Ян. «Аристотелевская силлогистика с точки зрения современной формальной логики». — М.: Издательство иностранной литературы, 1959.
• Хэмблин, Чарльз. «Computer Languages». — The Australian Journal of Science, 1957.
• Дейкстра, Эдсгер. «Algol 60 Translation: An Algol 60 Translator for the X1 and Making a Translator for Algol 60». — Mathematisch Centrum, 1961.
• Кнут, Дональд. «Искусство программирования. Том 1. Основные алгоритмы». — М.: Вильямс, 2010.