Польская нотация

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

История

Польская нотация была предложена польским логиком и математиком Яном Лукасевичем в 1920-х годах. Первоначально она разрабатывалась для упрощения записи формул в логике высказываний и исчислении предикатов. Лукасевич стремился создать бесскобочную запись, которая была бы однозначной и удобной для машинной обработки. В 1929 году он опубликовал работу «Elementy logiki matematycznej» (Элементы математической логики), где впервые систематически изложил префиксную нотацию.

В 1950-х годах, с развитием компьютерных наук и появлением первых компиляторов, польская нотация была адаптирована для использования в программировании. В 1954 году американский логик и программист Чарльз Хэмблин (Charles Hamblin) независимо предложил обратную польскую нотацию (постфиксную запись, где оператор следует за операндами). Эта модификация оказалась особенно удобной для реализации стековых вычислений и стала основой для многих языков программирования и калькуляторов.

Основные формы

Префиксная нотация (собственно польская нотация)

В префиксной нотации оператор записывается перед операндами. Количество операндов для каждого оператора фиксировано (бинарные операторы — два операнда, унарные — один). Примеры:

• Инфиксная запись: (3 + 4) × 5
• Префиксная запись: × + 3 4 5
• Инфиксная запись: sin(π/2)
• Префиксная запись: sin / π 2

Постфиксная нотация (обратная польская нотация, ОПН)

В постфиксной нотации оператор записывается после операндов. Пример:

• Инфиксная запись: (3 + 4) × 5
• Постфиксная запись: 3 4 + 5 ×

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

Алгоритмы преобразования

Из инфиксной в префиксную

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

1. Полностью расставить скобки в исходном выражении, явно указывая порядок операций.
2. Заменить каждый оператор на его префиксную форму, переместив его перед соответствующей парой скобок.
3. Удалить все скобки.

Пример: ( (3 + 4) × 5 ) → × ( + 3 4 ) 5 → × + 3 4 5.

Из инфиксной в постфиксную

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

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

Вычисление выражений

Вычисление постфиксной нотации

Вычисление выражения в постфиксной нотации выполняется с помощью стека:

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

Пример вычисления 3 4 + 5 ×:

• Чтение 3: стек = [3]
• Чтение 4: стек = [3, 4]
• Чтение +: извлечение 4 и 3, вычисление 3+4=7, стек = [7]
• Чтение 5: стек = [7, 5]
• Чтение ×: извлечение 5 и 7, вычисление 7×5=35, стек = [35]
• Результат: 35.

Вычисление префиксной нотации

Вычисление префиксной нотации выполняется аналогично, но чтение токенов происходит справа налево:

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

Применение

Компьютерные науки

• Компиляторы и интерпретаторы: обратная польская нотация используется на этапе генерации промежуточного кода (например, в байт-коде виртуальных машин). Многие языки программирования (Forth, PostScript, некоторые версии Lisp) используют постфиксную или префиксную нотацию как основную.
• Калькуляторы: инженерные калькуляторы Hewlett-Packard (HP) с 1970-х годов используют обратную польскую нотацию для ввода выражений. Это позволяет избежать использования скобок и знака равенства, ускоряя вычисления.
• Стековые машины: архитектуры, такие как Java Virtual Machine (JVM) и .NET Common Language Runtime (CLR), используют постфиксную нотацию для инструкций, работающих со стеком операндов.

Логика и математика

• Логика высказываний: префиксная нотация используется для записи формул в исчислении высказываний, например, Cpq (импликация p → q), Kpq (конъюнкция p ∧ q), Apq (дизъюнкция p ∨ q).
• Формальные грамматики: польская нотация применяется для описания синтаксиса языков программирования и математических выражений.

Экономика и финансы

• Финансовые модели: некоторые системы для расчёта сложных финансовых формул используют префиксную нотацию для упрощения парсинга и вычислений.

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

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

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

Недостатки

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

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

• Ян Лукасевич использовал заглавные латинские буквы для обозначения логических операций: C — импликация, K — конъюнкция, A — дизъюнкция, N — отрицание.
• В 1960-х годах компания Burroughs Corporation выпустила серию компьютеров B5000, которые использовали стековую архитектуру и обратную польскую нотацию на уровне машинных инструкций.
• Язык программирования Forth, созданный Чарльзом Муром в 1970 году, полностью основан на постфиксной нотации и стековой модели вычислений.
• В некоторых моделях калькуляторов HP (например, HP-35, HP-12C) до сих пор используется обратная польская нотация, что является предметом культа среди инженеров и финансистов.

Источники

• Лукасевич, Ян. «Elementy logiki matematycznej» (1929).
• Hamblin, Charles. «Computer Languages» (1957).
• Дейкстра, Эдсгер. «Algol 60 Translation» (1961).
• Кнут, Дональд. «Искусство программирования», том 2.
• Ахо, Альфред; Лам, Моника; Сети, Рави; Ульман, Джеффри. «Компиляторы: принципы, технологии и инструменты».