Перевод из инфиксной нотации в постфиксную. Обратная польская запись

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

Перевод выражений из инфиксной нотации в постфиксную

Для перевода из инфиксной нотации в постфиксную будем использовать переработанный автором статьи на хабре алгоритм Дейкстры. Нам понадобится стек, куда будем записывать математические операторы (программа, которую я приведу далее поддерживает только такие операторы: «+», «-«, «*», «/». Стек я буду использовать тот, который описывался в этой статье (немного модифицированный).

Давайте на примере переведем выражение (1+2)*4. Представим, что элементы выражения это вагоны поезда. Добавим в конец состава поезда вагон с символом «|», который говорит об окончании математического выражения. На схеме представленной ниже есть две станции: первая — Москва, куда попадают операторы, вторая — Киев, где будет формироваться выражение в постфиксной нотации.

obratnaya-polskaya-zapis

Вагоны содержащие операнды (числа или переменные, в этом примере разбираются только числа) направляются всегда в Киев и никогда не едут в Москву. Вагон с оператором перед стрелкой должен остановиться и узнать куда ему направляться. Для выбора направления давайте рассмотрим следующую таблицу (первая строка соответствует вагонам находящимся на стрелке, левый столбец — предыдущий вагон, отправившийся в Москву):

| + * / ( )
| 4 1 1 1 1 1 5
+ 2 2 2 1 1 1 2
2 2 2 1 1 1 2
* 2 2 2 2 2 1 2
/ 2 2 2 2 2 1 2
( 5 1 1 1 1 1 3

Числа соответствуют следующим ситуациям:

  1. Вагон на стрелке отправляется в Москву
  2. Последний вагон, направившийся в Москву, разворачивается и направляется в Киев
  3. Вагон, находящийся на стрелке, и последний вагон, отправившийся в Москву, угоняются и исчезают
  4. Остановка. Символы, находящиеся на Киевской ветке, представляют собой формулу в обратной польской записи, если читать слева направо
  5. Остановка. Произошла ошибка. Изначальная формула была некорректно сбалансирована

И так, на примере нашего выражения (1+2)*4, давайте смоделируем движение вагонов. Первый вагон попавший на стрелку — «(«, на данный момент в стеке (в Москве) нет никаких элементов, смотрим в табличку, видим, если открывающая скобка идет первой, то отправляем её в Москву.

Киев
Москва (

Следующий вагон это число 1, все числа мы без раздумий направляем в Киев.

Киев 1
Москва (

Далее идет  «+», на данный момент предыдущий вагон, направившийся в Москву это — «(«, смотрим в таблицу, знак сложения после скобки направляется в Москву. Далее число 2 — в Киев.

Киев 1 2
Москва ( +

Plan_2

После идет закрывающая скобка — «)», предыдущий вагон — «+», смотрим в таблицу, видим, что последний вагон направившийся в Москву должен развернуться и направиться в Киев — помещаем наш «+» в Киев (теперь в Киеве у нас такая ситуация: 1 2 +).

Киев 1 2 +
Москва (

Внимание, так как не сказано, что вагон с «)» надо куда-то направить, мы снова смотрим в таблицу,  теперь последний вагон в Москве — «(«, смотрим в таблицу, видим, что вагоны надо убрать. Удаляем вагон «(» со стека (с Москвы), и перегоняем на стрелку следующий вагон — «*», на данный момент у нас станция Москва пустая, получается что вагон идет первым, смотрим в табличку — знак умножения, если тот первый, направляется в Москву.

Киев 1 2 +
Москва *

Следующий вагон на стрелке — «4» — в Киев! 

Киев 1 2 + 4
Москва *

Теперь на стрелку попал последний вагон «|», смотрим в табличку, видим, что если последний вагон в Москве «*», а на стрелке «|», то «*» разворачиваем и направляем с Москвы в Киев.

Киев 1 2 + 4 *
Москва

На стрелке по прежнему остался «последний вагон», в стеке нет ничего, на пересечении «|» и «|» — цифра 4 — преобразование завершено. В Киеве сейчас такая ситуация: 2 + 4 *.

Вычисление выражения в обратной польской записи

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

Шаг ОПЗ Стек с операндами
Исходные значения 1 2 + 4 *
1 2 + 4 * 1
2 + 4 * 1, 2
3 4 * 3 Суммируем два последних числа
4 * 3, 4
5 12 Перемножаем два последних числа

Теперь пример по сложнее, рассмотрим выражение 8 2 5 * + 1 3 2 * + 4 — /, что в инфиксной нотации соответствует выражению ( 8 + 2 * 5 ) / ( 1 + 3 * 2 — 4 ):

Шаг Обратная польская запись Стек с операндами
Исходные значения 8 2 5 * + 1 3 2 * + 4 — /
1 2 5 * + 1 3 2 * + 4 — / 8
2 5 * + 1 3 2 * + 4 — / 8, 2
3 * + 1 3 2 * + 4 — / 8, 2, 5
4 + 1 3 2 * + 4 — / 8, 10 Умножаем 2 на 5
5  1 3 2 * + 4 — / 18 Суммируем 8 и 10
6 3 2 * + 4 — / 18, 1
7 2 * + 4 — / 18, 1, 3
8 * + 4 — / 18, 1, 3, 2
9 + 4 — / 18, 1, 6 Умножаем 3 на 2
10 4 — / 18, 7 Суммируем 1 и 6
11 — / 18, 7, 4
12 / 18, 3 Вычитаем из 7 4
13 6 Делим 18 на 3

Реализация программы на С++

Реализация довольна проста, для перевода нам необходимо запрограммировать только таблицу, а для счета — цикл, стек и пара условий. Заголовочный файл, стек и графический интерфейс я разбирать не буду. Про стек можете прочитать здесь. Все исходные коды рабочей программы будут приведены нижу. Начнем пожалуй с перевода из инфиксной нотации в постфиксную. Чтобы упростить себе жизнь элементы математического выражения будем вводить через пробел. Для этого я создал функцию convert, которая в качестве формального параметра принимает строку в инфиксной нотации, а, как результат, возвращает строку в постфиксной нотации:

stk — объект класса stack, который хранит в себе элементы строкового типа данных QString, в данном контексте предназначен для хранения операторов

Счетчик i увеличиваем только в том случае, если вагон, который стоит на стрелке куда-то отправляется (в таблице пункты 1 и 3). Чтоб понять как работает данный код прокомментирую более подробно следующий кусок:

И так, допустим на стрелку пришел вагон с «+». Теперь далее, согласно таблице добавить в стек (отправить в Москву) мы можем только, если на данный элемент стек пустой, либо, если последний добавленный в стек элемент это открывающая скобка «(«. После добавления элемента в стек мы переходим к следующему. За все это отвечает следующая строка:   if(first==»-1″ || first==»(«){ stk->add(inf[i]); i++;}. Смотрим снова в таблицу, видим, что если на стрелке «+», а на вершине стека «+», «-«, «*» или «/», то мы элемент на вершине стека (последний добавленный в него элемент) направить в Киев (в строку где формируется обратная польская запись). За это отвечает следующая строка: if(first==»+» || first==»-» || first==»*» || first==»/») post.append(stk->take());.

Теперь вычисление обратной польской записи. Функция calc, в качестве формального параметра принимает строку с выражением в постфиксной нотации, как результат, возвращает число формата float:

 

stk_digit — объект класса stak_digit , который хранит в себе элементы типа данных float, в данном контексте предназначен для хранения операндов.

Далее вы можете скачать программу, которая демонстрирует работу этих функций. В данном примере эти функции являются методами класса MainWindow, по этому я писал вместо float calc(QString postf) — float MainWindow::calc(QString postf).

Преобразование и вычисление обратной польской записи

Выражения для тестирования

Инфиксная нотация Обратная польская запись Ответ
( 8 + 2 * 5 ) / ( 1 + 3 * 2 — 4 ) 8 2 5 * + 1 3 2 * + 4 — / 6
( 1 + 2 ) * 4 + 3 1 2 + 4 * 3 + 15
( 15 / 3 + 11 — 3 * 5 ) / 3.2 * ( 5.6 — 10 ) 15 3 / 11 + 3 5 * — 3.2 / 5.6 10 — * -1.375

За основу взята статья на хабрахабре, от автора GORKOFF


  • Александр

    День добрый) делал лабы на пайтоне, переточил Ваш код в пайтон, если пригодится могу прислать.
    С уважением,
    Александр

    • wollk

      Спасибо большое, но не стоит, я с питоном еще ни разу не работал

    • Роман

      сбросьте мне, интересно будет посмотреть на реализацию

  • Pios Sobachii

    Ваш код абсолютно не читаемый. Отформатируйте его, пожалуйста.

    • wollk

      Все лень было переделывать, редактор все испортил. Вы заставили ))) Спасибо за замечание!

    • wollk

      И можете скачать исходники, в любимом редакторе проще разбирать 😉

  • Владислав Колодка

    Для чего нужна вертикальная синяя колонка в

    таблице выбора движения?

    • wollk

      Забыл вам ответить, в день, когда вы оставили комментарий ;(
      Если мне память не изменяет, то первая строка соответствует вагонам находящимся на стрелке, левый столбец — предыдущий вагон, отправившийся в Москву.

  • eHoT

    Возможно ли выложить скомпилированный вариант?. Нет возможности поставить QT Creator.

    • http://master.virmandy.net/OPZ—compiled Пробуйте, запустится или нет

      • eHoT

        Не надеялся на ответ (О_О) Не запустило так как у меня Виндосос((

        • У меня тоже Windows. 10 я версия.
          Тогда увы, идей нету ( Если Вам нужно просто перевести с инфиксной нотации в постфиксную, то воспользуйтесь онлайн сервисами.

          • eHoT

            Если у вас то же винтовс, то странно, почему тогда не запустилась. По ошибке видно что не хватает плагина.

          • Странно, я скопировал все библиотеки. В таком случае, к сожалению, помочь ничем не могу ( Качайте Qt.

      • eHoT

        Спасибо что ответили.

  • Denis Timchuk

    Вы взяли плохой пример для алгоритма , на много лучше ,хотя бы, такой:
    2+3*4/2