1.3. Алгоритм перевода выражений в польскую запись
Алгоритм работает в соответствии со схемой, показанной на рис. 3.
Здесь посимвольно слева направо анализируется входная строка, которая содержит исходное выражение, представленное в инфиксной форме. Операнды переписываются непосредственно в выходную строку, содержащую польскую запись выражения, а операторы заносятся в стек. При этом в зависимости от приоритета операций они могут вытолкнуть из стека в выходную строку другие операторы. Приоритеты операторов для арифметических выражений даны в табл. 1.
Таблица 1
-
Значение приоритета p[s[i]]
0
1
2
Операторы (символы s[i])
( , )
+ , –
, /
Пусть s[i] - анализируемый i-й символ входной строки, Store[top] - верхний элемент стека. Тогда алгоритм перевода выражений в польскую запись можно представить в виде следующей последовательности шагов.
Шаг 1. Если анализируемый символ s[i] входной строки является операндом, то он переписывается в выходную строку.
Шаг 2. Если s[i] является оператором, который имеет больший приоритет, чем оператор в вершине стека, т.е. p[s[i]]>p[Store[top]], то символ s[i] записывается в стек. В противном случае, т.е. если p[s[i]] p[Store[top]], то из стека сначала последовательно выбираются и помещаются в выходную строку операторы, имеющие приоритет больший или равный p[s[i]], а затем символ s[i] записывается в стек.
Шаг 3. Если анализируемый символ s[i] = "(", то он помещается в стек, не выталкивая при этом ни одного оператора.
Шаг 4. Если s[i] = ")", то из стека выталкиваются и записываются в выходную строку все операторы до первого встретившегося символа "(". Символы "(" и ")" уничтожают друг друга и в выходную строку не включаются.
Шаг 5. Шаги 1-4 повторяются до тех пор, пока не будут просмотрены все символы входной строки. Затем оставшиеся в стеке операторы переносятся в выходную строку.
В качестве примера рассмотрим формирование польской записи для выражения (1). Процесс работа алгоритма представлен в табл. 2.
Таблица 2
-
Шаг алгоритма
1
2
3
4
5
6
7
8
9
10
Входная строка
(
a
-
b
)
*
c
+
d
Состояние стека
(
#
(
#
-
(
#
-
(
#
#
*
#
*
#
+
#
+
#
#
Выходная строка
a
b
‑
c
*
d
+
Символ # выполняет роль вспомогательного оператора c нулевым приоритетом, который всегда находится в cтеке и необходим для корректного выполнения второго пункта алгоритма в том случае, когда стек пуст. Результатом является следующая строка польской записи: a b – c d + .