Обратная польская нотация, получение и вычисление⁠⁠

Предыдущая статья: Включения действий при разборе и итог пройденных тем в vk.com

Статья для повторения: От перепутья к перепутью, часть вторая: Разбор языка арифметики

Для тех кто спешит увидеть код вот (С#) или псевдокод вот, кому нужна ясность в них читаем далее.

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

Ниже показаны ещё примеры:

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

Получение ОПН из инфиксной записи

Используем рекурсивный спуск по рассмотренной нами грамматике, где в качестве чисел целые без знака:

Грамматика с унарным минусом и плюсом:
Г: В -> ДС
С -> ε | +ДС | -ДС
Д -> РП | -Д | +Д
П -> ε | *РП | /РП
Р -> ч | (В)

Звенья цепочки ОПН опишем набором трёх типов:
1. Операнд - целые числа.
2. Одноместный оператор - однооп, это унарный минус и плюс.
3. Двуместный оператор - двуоп, это минус, плюс, умножить, делить.

Ниже представлено полное описание звена ОПН:

Соберём звенья в список, который будет представлять нашу ОПН. Для этого отметим 3 действия на отделах рисунка порядка:
Д1 - Создать хрон. Переменная хранящая звено до момента добавления в список.
Д2 - Запомнить. Помещаем встреченное звено в хрон.
Д3 - Добавить. Записываем в список ОПН.

Ниже показаны отделы и процедуры со встроенными действиями в разбор:

Так мы добавляем в первую очередь операнды, затем операторы в порядке их приоритетов. Всмотритесь в процедуру «Дополнениее». В качестве хрона используется стог (англ. stack), так как запоминаются несколько знаков сразу, их следует вспомнить в обратном порядке.

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

Грамматика обратной польской нотации:
Г:В -> ч | П`П
П`-> чПО
П -> ВОП | ε

где:

В - ВЫРАЖЕНИЕ
О - ОПЕРАТОР
П - ПРАВОЕ_ПОДВЫРАЖЕНИЕ
П`- ПОДВЫРАЖЕНИЕ
ч - ЧИСЛО

Остановитесь на минутку, осмыслите.

Вычисление ОПН

Ниже изображена схема устройства вычисления ОПН - Стог-машина (Stack machine), а на следующем её описание. Для примера использована ОПН:

1 2 3 * + 4 -

Которая получена из инфиксной записи:

1 + 2 * 3 - 4

Стог-машина состоит из:

1. Стога - в котором хранятся промежуточные значения.

2. Набора двухместных и одноместных операций.

3. Движка - который читает ОПН, управляет стогом и обращается к набору операций.

ОПН обладает свойством: действия применяются последовательно при её чтении, на чём и основана работа стог-машины:

1. Если звено операнд, то кладём число в стог.

2. Если звено однооп, снимаем верхнее число обрабатываем, итог кладём в стог.

3. Если звено двуоп, снимаем два верхних числа и применяем операцию. Причём первое значение операции - второе верхнее, а второе - первое верхнее. Итог кладём в стог.

4. По окончанию чтения ОПН, итог вычисления оказывается на дне стога, одним.

В заключении

Не стоит думать, что рассмотренный способ единственный для получения ОПН. Есть так же алгоритм Дейкстры перевода выражения в ОПН, но я не знаю стоит ли его разобрать или сразу перейти к обсуждению включения действий в «Провидца», ранее нами рассматриваемого.

Поэтому решение будет зависить от вас:

Ну на это всё, быть добру, хорошего настроения. Подписывайся. =)
Точно! Для любознательных и внимательных читателей, ещё одна не позиционная система счисления.