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

Машина фон Неймана
Реальные вычислители, построенные согласно архитектурным принципам фон Неймана, следуют дополнительному соглашению: команды и их аргументы записываются в строго определённом порядке:

Высокоуровневые языки
Высокоуровневый язык программирования — язык программирования, разработанный для быстроты и удобства использования.
Конструкции высокоуровневых языков, как правило, более приближены к конструкциям естественного языку современной математики.

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

Математические выражения
Каждое математическое выражение можно представить в трех специфических видах записи:
Инфиксная нотация — это форма математических записей, которую использует большинство людей: левый операнд, знак действия, правый операнд. Например: 3 + 4 или 3 + 4 * (2 - 1).
Префиксная нотация — сначала пишется действие, затем левый операнд, затем правый операнд. Для выражения «a+b» префиксная запись будет иметь вид: «+ab». Выражению «a+b*(c+d)» соответствует запись «+a*b+cd».
Постфиксная нотация — сначала идёт левый операнд, потом правый операнд, затем знак операции. Для выражения «a+b» постфиксная запись имеет вид «ab+». Выражению «a+b*(c+d)» соответствует запись «abcd+*+».

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

Дерево выражения

Обратная польская нотация
Наибольшее распространение при решении практических задач получил метод тpансляции выражений с помощью обpатной польской записи, котоpую пpедложил польский математик Ян Лукашевич.
Обратная польская нотация (RPN, англ. Reverse Polish Notation) — форма бесскобочной записи математических выражений согласно постфиксной нотации.

Трансляция выражений

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

Обратная польская нотация
Здесь X и Y – вспомогательные пеpеменные.

Алгоритм Дейкстры
В ноябре 1961 г. Эдсгер Вибе Дейкстра опубликовал алгоритм для преобразования выражений из инфиксной нотации в RPN.

Приоритеты операций
Зададим приоритеты используемых операций:

Алгоритм Дейкстры
Базовые правила:
Исходная стpока символов просматривается слева напpаво.
Опеpанды сразу пеpеписываются в выходную стpоку.
Знаки опеpаций заносятся в стек.

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

Алгоритм Дейкстры. Пример.

Контрольные вопросы
1. Какая запись представляет собой обратную польскую нотацию выражения «A+B*(C-D)»?
A+B*C-D
ABCD-*+
+A*B-CD
2. Кто из учёных ввёл понятие обратной польской нотации?
Эдсгер Дейкстра
Джон фон Нейман
Ян Лукашевич

Постановка задачи
Написать программу, преобразующую инфиксную нотацию в RPN и обратно. При этом, программа должна сама определять нотацию по виду входной строки. Нотацией «по умолчанию» считается инфиксная.
Примеры работы программы (знак ? указывает, что далее следует результат выполнения программы):
dijkstra.js a+b/(c-d) ? abcd-/+
dijkstra.js abcd-/+ ? a+b/(c-d)
Запуск программы без аргументов выводит сообщение с информацией о программе и вариантах запуска.

Постановка задачи
Кроме того, программа должна уметь обрабатывать типовые ошибки, указывая при выводе конкретный тип (или код) ошибки:
пропуск скобки: «(a+b» или «a+(b+c)», выражения «((a+b))», «a/(b)», «(((а)))» считаются корректными;
пропуск операнда (оператора): «a+», «a/()», «ab»;
повтор операнда (оператора): «aa+b», «a++b», «i++»;
некорректный ввод: «привет!», «$#@» и т.п.