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

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

История

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

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

Принцип работы

В основе ОПН лежит работа со стеком — структурой данных, работающей по принципу LIFO (Last In, First Out, «последним пришёл — первым ушёл»). Алгоритм вычисления выражения в ОПН выглядит следующим образом:

1. Чтение токенов (чисел и операторов) слева направо.
2. Если токен — число (операнд), он помещается (пушится) в стек.
3. Если токен — оператор, из стека извлекаются (попаются) два верхних операнда (для бинарных операций). К ним применяется оператор, и результат помещается обратно в стек.
4. После обработки всех токенов в стеке остаётся единственное значение — результат вычисления.

Например, выражение 3 4 + 5 * вычисляется так:

• Читаем 3 — пушим в стек: [3]
• Читаем 4 — пушим в стек: [3, 4]
• Читаем + — извлекаем 4 и 3, складываем, получаем 7, пушим: [7]
• Читаем 5 — пушим в стек: [7, 5]
• Читаем * — извлекаем 5 и 7, умножаем, получаем 35, пушим: [35]
• Результат: 35. В инфиксной записи это выражение выглядело бы как (3 + 4) * 5.

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

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

• Отсутствие скобок: Порядок операций определяется исключительно последовательностью, что упрощает синтаксический анализ и делает запись более компактной.
• Простота машинной реализации: Алгоритм вычисления ОПН чрезвычайно прост и эффективен, не требует рекурсии или сложных структур данных, кроме стека. Это делает его идеальным для встроенных систем, калькуляторов и низкоуровневого программирования.
• Однозначность: Каждое выражение в ОПН имеет единственную интерпретацию, в отличие от инфиксной записи, где требуется знание приоритетов операторов.
• Эффективность: Вычисление ОПН происходит за один проход по выражению, что минимизирует вычислительные затраты.

Недостатки

• Нечитаемость для человека: Для большинства людей инфиксная запись (с привычными скобками и приоритетами) интуитивно понятнее. Чтение и написание длинных выражений в ОПН требует тренировки.
• Сложность отладки: Ошибки в порядке операндов или операторов могут быть неочевидны, особенно в сложных формулах.
• Необходимость знания арности операторов: Алгоритм должен знать, сколько операндов требует каждый оператор (бинарный, унарный и т.д.), что может усложнить реализацию для нестандартных функций.

Применение

ОПН нашла применение в нескольких ключевых областях:

Калькуляторы

Наиболее известное применение — программируемые и инженерные калькуляторы, особенно от Hewlett-Packard (HP). Многие модели HP (HP-35, HP-12C, HP-48) используют ОПН как основной метод ввода. Пользователи ценят её за скорость и возможность выполнять цепочки вычислений без нажатия клавиши равенства после каждой операции. Также ОПН используется в некоторых программных калькуляторах (например, в утилите dc в Unix-подобных системах).

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

ОПН является промежуточным представлением кода при компиляции. Многие компиляторы сначала преобразуют инфиксное выражение в постфиксную форму (алгоритм сортировочной станции Эдсгера Дейкстры), а затем генерируют машинный код или байт-код, который легко выполняется на стековой виртуальной машине. Например, виртуальная машина Java (JVM) и среда .NET CLR используют стековую архитектуру, близкую к принципам ОПН.

Стековые языки программирования

Существуют языки программирования, полностью основанные на ОПН. Наиболее известные из них:

• Forth: Разработан в 1960-х годах для встроенных систем. Программа на Forth представляет собой последовательность слов (команд), которые манипулируют стеком.
• PostScript: Язык описания страниц, используемый в принтерах и графических системах. Команды PostScript также работают со стеком и записываются в постфиксной форме.
• Factor: Современный стековый язык, сочетающий идеи ОПН с функциональным программированием.

Обработка данных

В некоторых системах обработки данных (например, в базах данных или системах логического вывода) ОПН используется для представления и вычисления логических или арифметических условий.

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

• Алгоритм сортировочной станции: Эдсгер Дейкстра в 1961 году разработал алгоритм, который преобразует инфиксное выражение в постфиксное (ОПН). Название алгоритма происходит от аналогии с железнодорожной сортировочной станцией, где вагоны (операнды и операторы) переставляются в нужном порядке.
• Ошибка в названии: Исторически термин «обратная польская нотация» является неточным. Ян Лукасевич изобрёл префиксную нотацию (польскую). Постфиксная версия — это её «обратная» форма, поэтому название «обратная польская» закрепилось именно за ней.
• Калькулятор HP-35: Первый карманный научный калькулятор HP-35 (1972) использовал ОПН. Его появление произвело революцию в инженерных расчётах, позволив отказаться от логарифмических линеек. HP-35 мог выполнять сложные вычисления с тригонометрическими и логарифмическими функциями, используя стек из четырёх регистров.
• Культовый статус: Калькуляторы HP с ОПН (особенно HP-12C для финансовых расчётов) приобрели культовый статус среди профессионалов. Многие пользователи, привыкшие к ОПН, считают её единственно правильным способом ввода выражений.

Источники

• Ян Лукасевич, «Аристотелевская силлогистика с точки зрения современной формальной логики» (1951)
• Чарльз Хэмблин, «Компьютерная арифметика» (1957)
• Эдсгер Дейкстра, «Алгоритм сортировочной станции» (1961)
• Документация Hewlett-Packard к калькуляторам HP-35, HP-12C, HP-48
• Статья «Reverse Polish notation» в англоязычной Википедии
• Материалы по языку Forth (стандарт ANS Forth)