Mathos

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

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

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

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

Звенья цепочки ОПН опишем набором трёх типов:
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. По окончанию чтения ОПН, итог вычисления оказывается на дне стога, одним.

В заключении

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

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

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

Условимся что, автомат принимает вместо пустой цепочки ε, конечный символ ⊥, который будет означать конец принимаемой цепочки. Подобным образом обрабатываются строки в языке C, в нём используется так называемый нуль-терминал или по-русски нуль-концевик.

Теперь возьмём и заменим вспомогательные символы в графе на точки, а символы основного алфавита наоборот выделим в круги.

Теперь мы можем наблюдать два столпа программирования ветвление и цикл, а так же последовательность их выполнения. На рисунке порядка они отчётливо отображены, что позволяет легко описать в коде алгоритм:

Определённо вы заметили, что этот код можно упростить, а это намекает нам и на то, что можно упростить и рисунок порядка. Что же займёмся этим:

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

На этом тема закрыта, но! Должен отметить тема синтаксических диаграмм, пока-что до конца не описана, мы её коснёмся ещё раз, но уже при рассмотрении КС-грамматик.

З.Ы, Подписывайтесь рофлов ради, али кринжов. Ну или из любопытства. Хорошего настроения.