Перевод в ОПЗ арифметических и логических выражений

Метод, который мы с вами рассмотрим, был предложен в 1960 году голландским ученым, которого зовут Эдсгер Вибе Дейкстра (Edsger Wybe Dijkstra).

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

Каждому ограничителю, входящему в выражение, присваивается приоритет.

Операция ИЗ – изменение знака, а Ф – вызов функции.

Арифметическое выражение просматривается слева направо.

Операнды переписываются в выходную строку, а знаки операций помещаются в стек операций.

Выходная строка Операнды Входная стока

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

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

После окончания входной строки происходит выталкивание всех оставшихся в стеке символов и дописывание их к выходной строке.

Пример 1. Привести в обратную польскую запись арифметическое выражение:

a + b * c – d / (a + b)

a b c * + d a b + / -

Пример 2. Перевести логическое выражение

a + b > -5 and z – d = 1 + q ^ 2

a b + 5 ИЗ > z d – 1 q 2 ^ + = and