Обратная польская запись: элегантная альтернатива для вычисления математических выражений
Обратная польская запись (ОПЗ) — это эффективный метод вычисления математических выражений, отличающийся размещением операторов после операндов. Такой подход позволяет отказаться от использования скобок, упрощая и проясняя процесс вычислений. Хотя на первый взгляд это может показаться непривычным, использование ОПЗ значительно ускоряет выполнение операций, особенно в компьютерных системах и программируемых калькуляторах.
Существует множество способов записи математических выражений. Наиболее распространенным является инфиксная нотация, где операторы размещаются между операндами, как, например, в 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 — «последним вошел, первым вышел»).
Пошаговое вычисление выражения ОПЗ:
3: Читаем3. Это операнд, помещаем его в стек. Состояние стека:[3]4: Читаем4. Также операнд, помещаем его в стек. Состояние стека:[3, 4]+: Читаем оператор+. Извлекаем два операнда из стека (сначала4, затем3). Выполняем сложение:3 + 4 = 7. Помещаем результат (7) обратно в стек. Состояние стека:[7]2: Читаем2. Операнд, помещаем в стек. Состояние стека:[7, 2]: Читаем оператор. Извлекаем два операнда из стека (сначала2, затем7). Выполняем умножение:7 2 = 14. Помещаем результат (14) обратно в стек. Состояние стека:[14]5: Читаем5. Операнд, помещаем в стек. Состояние стека:[14, 5]-: Читаем оператор-. Извлекаем два операнда из стека (сначала5, затем14). Выполняем вычитание:14 - 5 = 9. Помещаем результат (9) обратно в стек. Состояние стека:[9]
Поскольку мы достигли конца выражения ОПЗ и в стеке остался только один элемент, этот элемент является окончательным результатом. Таким образом, значение выражения (3 + 4) 2 - 5, вычисленного в ОПЗ, равно 9.
Как преобразовать инфиксные выражения в ОПЗ?
Наиболее распространенным алгоритмом для преобразования инфиксных выражений в ОПЗ является алгоритм сортировочной станции, разработанный Эдсгером Дейкстрой. Этот алгоритм использует стек (для операторов и скобок) и выходную очередь (которая на практике может быть просто списком) для преобразования.
Шаги алгоритма сортировочной станции:
- Токенизация: Разбиваем инфиксное выражение на токены (числа, операторы, скобки).
- Инициализация: Создаем пустой стек для хранения операторов и пустую выходную очередь для построения выражения ОПЗ.
- Обработка токенов: Перебираем токены:
- Число: Если токен — число, добавляем его в выходную очередь.
- Оператор (op1): Если токен — оператор:
- Пока на вершине стека есть оператор (op2), И либо:
- op2 имеет более высокий приоритет, чем op1, ИЛИ
- op2 имеет равный приоритет с op1 И op1 левоассоциативен (в нашем примере все операторы левоассоциативны),
- Извлекаем op2 из стека и добавляем в выходную очередь.
- Помещаем op1 в стек.
- Пока на вершине стека есть оператор (op2), И либо:
- Левая скобка
(: Помещаем ее в стек. - Правая скобка
):- Пока оператор на вершине стека не является левой скобкой:
- Извлекаем оператор из стека и добавляем в выходную очередь. (Если стек становится пустым до того, как найдена левая скобка, значит, скобки не согласованы.)
- Если на вершине стека есть левая скобка, извлекаем ее из стека (но не добавляем в выходную очередь — скобки не включаются в выражение ОПЗ).
- Если после обработки правой скобки на вершине стека нет левой скобки, значит, скобки не согласованы.
- Пока оператор на вершине стека не является левой скобкой:
- Очистка стека: Когда больше нет токенов для чтения, извлекаем все оставшиеся операторы из стека и добавляем их в выходную очередь.
- Результат: Выходная очередь теперь содержит выражение ОПЗ.
Приоритет и ассоциативность:
Понимание приоритета и ассоциативности операторов важно. Обычный порядок приоритета (от высшего к низшему):
- Умножение (
), Деление (/) - Сложение (
+), Вычитание (-)
Все четыре основные арифметические операции являются левоассоциативными, что означает, что операторы с одинаковым приоритетом вычисляются слева направо (например, 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 -.
Заключение
Обратная польская запись — это элегантный и эффективный метод для записи и вычисления математических выражений. Хотя на первый взгляд она может показаться менее интуитивной, чем инфиксная нотация, ОПЗ предлагает ряд преимуществ, особенно для компьютерной обработки. Она устраняет неоднозначность, не требует скобок и может быть эффективно вычислена с использованием простого стека. Алгоритм сортировочной станции представляет собой широко используемый и эффективный метод преобразования инфиксных выражений в ОПЗ.
Ее историческое значение неоспоримо, поскольку она сыграла важную роль в ранних карманных калькуляторах и остается актуальной концепцией в информатике сегодня, используясь в компиляторах и виртуальных машинах. Будучи менее распространенной в повседневном использовании, ОПЗ является ценным инструментом и способом мышления, который обеспечивает более глубокое понимание взаимосвязи между математическими выражениями и компьютерными операциями.
