Обратная польская запись: элегантная альтернатива для вычисления математических выражений

Gábor Bíró • 2 марта 2025 г.
6 мин. чтения

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

Обратная польская запись: элегантная альтернатива для вычисления математических выражений
Источник: Авторская работа

Существует множество способов записи математических выражений. Наиболее распространенным является инфиксная нотация, где операторы размещаются между операндами, как, например, в A + B или (C D) - E. Хотя эта нотация может показаться интуитивно понятной для нас, людей, она не всегда является оптимальным решением для компьютеров и калькуляторов. В этой статье мы рассмотрим менее известную, но, возможно, более элегантную альтернативу: обратную польскую запись (ОПЗ), также известную как постфиксная нотация.

Что такое обратная польская запись?

ОПЗ — это математическая нотация, в которой операторы следуют за своими операндами. Вместо того чтобы писать A + B, в ОПЗ мы обозначаем это как A B +. На первый взгляд это может показаться необычным, но ее преимущества быстро становятся очевидными.

Концепция ОПЗ берет свое начало от польского математика Яна Лукасевича, который в 1920-х годах разработал префиксную нотацию (польскую нотацию), где операторы предшествуют своим операндам. Постфиксная нотация является вариацией этого, которая была далее развита австралийским ученым-компьютерщиком Чарльзом Хэмблином в 1950-х годах для упрощения компьютерной обработки.

Почему ОПЗ полезна?

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

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

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

Как работает ОПЗ

Давайте рассмотрим пример того, как работает ОПЗ. Рассмотрим инфиксное выражение: (3 + 4) 2 - 5.

Сначала преобразуем это в ОПЗ. Для преобразования необходимо учесть порядок операций. В данном случае сначала выполняем сложение в скобках, затем умножение на два и, наконец, вычитание пяти. Выражение в ОПЗ будет выглядеть так: 3 4 + 2 5 -.

Теперь давайте посмотрим, как вычислить это выражение ОПЗ, используя стек. Стек — это структура данных, в которую элементы можно помещать (push) и удалять (pop), при этом всегда извлекая последний вставленный элемент первым (LIFO — «последним вошел, первым вышел»).

Пошаговое вычисление выражения ОПЗ:

  1. 3: Читаем 3. Это операнд, помещаем его в стек. Состояние стека: [3]
  2. 4: Читаем 4. Также операнд, помещаем его в стек. Состояние стека: [3, 4]
  3. +: Читаем оператор +. Извлекаем два операнда из стека (сначала 4, затем 3). Выполняем сложение: 3 + 4 = 7. Помещаем результат (7) обратно в стек. Состояние стека: [7]
  4. 2: Читаем 2. Операнд, помещаем в стек. Состояние стека: [7, 2]
  5. : Читаем оператор . Извлекаем два операнда из стека (сначала 2, затем 7). Выполняем умножение: 7 2 = 14. Помещаем результат (14) обратно в стек. Состояние стека: [14]
  6. 5: Читаем 5. Операнд, помещаем в стек. Состояние стека: [14, 5]
  7. -: Читаем оператор -. Извлекаем два операнда из стека (сначала 5, затем 14). Выполняем вычитание: 14 - 5 = 9. Помещаем результат (9) обратно в стек. Состояние стека: [9]

Поскольку мы достигли конца выражения ОПЗ и в стеке остался только один элемент, этот элемент является окончательным результатом. Таким образом, значение выражения (3 + 4) 2 - 5, вычисленного в ОПЗ, равно 9.

Как преобразовать инфиксные выражения в ОПЗ?

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

Шаги алгоритма сортировочной станции:

  1. Токенизация: Разбиваем инфиксное выражение на токены (числа, операторы, скобки).
  2. Инициализация: Создаем пустой стек для хранения операторов и пустую выходную очередь для построения выражения ОПЗ.
  3. Обработка токенов: Перебираем токены:
    • Число: Если токен — число, добавляем его в выходную очередь.
    • Оператор (op1): Если токен — оператор:
      • Пока на вершине стека есть оператор (op2), И либо:
        • op2 имеет более высокий приоритет, чем op1, ИЛИ
        • op2 имеет равный приоритет с op1 И op1 левоассоциативен (в нашем примере все операторы левоассоциативны),
      • Извлекаем op2 из стека и добавляем в выходную очередь.
      • Помещаем op1 в стек.
    • Левая скобка (: Помещаем ее в стек.
    • Правая скобка ):
      • Пока оператор на вершине стека не является левой скобкой:
        • Извлекаем оператор из стека и добавляем в выходную очередь. (Если стек становится пустым до того, как найдена левая скобка, значит, скобки не согласованы.)
      • Если на вершине стека есть левая скобка, извлекаем ее из стека (но не добавляем в выходную очередь — скобки не включаются в выражение ОПЗ).
      • Если после обработки правой скобки на вершине стека нет левой скобки, значит, скобки не согласованы.
  4. Очистка стека: Когда больше нет токенов для чтения, извлекаем все оставшиеся операторы из стека и добавляем их в выходную очередь.
  5. Результат: Выходная очередь теперь содержит выражение ОПЗ.

Приоритет и ассоциативность:

Понимание приоритета и ассоциативности операторов важно. Обычный порядок приоритета (от высшего к низшему):

  • Умножение (), Деление (/)
  • Сложение (+), Вычитание (-)

Все четыре основные арифметические операции являются левоассоциативными, что означает, что операторы с одинаковым приоритетом вычисляются слева направо (например, a - b - c = (a - b) - c).

Пример преобразования инфиксного выражения (3 + 4) 2 - 5 в ОПЗ с использованием алгоритма сортировочной станции:

Токен Выходная очередь Стек операторов Примечание
( ( Левая скобка помещена в стек.
3 3 ( Число добавлено в выходную очередь.
+ 3 (, + Оператор помещен в стек.
4 3, 4 (, + Число добавлено в выходную очередь.
) 3, 4, + ( Правая скобка: извлекаем операторы (+) в очередь, пока не будет найдена левая скобка. Извлекаем левую скобку.
3, 4, + Оператор помещен в стек (стек был пуст).
2 3, 4, +, 2 Число добавлено в выходную очередь.
- 3, 4, +, 2, - Оператор: в стеке имеет более высокий приоритет, извлекаем в очередь. Помещаем - в стек.
5 3, 4, +, 2, , 5 - Число добавлено в выходную очередь.
End 3, 4, +, 2, , 5, - Конец ввода: извлекаем оставшиеся операторы (-) из стека в очередь.

Таким образом, формой ОПЗ инфиксного выражения (3 + 4) 2 - 5 является: 3 4 + 2 * 5 -.

Заключение

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

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

Gábor Bíró • 2 марта 2025 г.