Польская запись

[azl-8]

Здравствуйте! Мне нужно составить блок-схему алгоритма вычисления арифметических выражений в польской записи. Данный алгоритм имеет следующий вид:
В основе алгоритма получения польской записи лежит следующая схема:



Рисунок 1 – Схема перевода выражений в польскую запись.

Здесь посимвольно слева направо анализируется вход¬ная строка, которая содержит исходное выражение, представленное в инфиксной форме. Операнды переписываются непосредственно в выход¬ную строку, содержащую польскую запись выражения, а операторы за¬носятся в стек. При этом в зависимости от приоритета операций они могут вытолкнуть из стека в выходную строку другие операторы. Приоритеты операторов для арифметических выражений даны в таблице 1.
Значение приоритета P(S(I)) 1 2 3
Операторы (символы S(I)) (,) +,– ,/(mod, div)




Пусть S(I) - анализируемый I -й символ входной строки, SТОRЕ(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) запи¬сывается в cтек.
3. Если анализируемый символ S(I) ="(", то он помещается в стек, не выталкивая при этом ни одного оператора.
4. Если S(I) =")", то из стека выталкиваются и записывают¬ся в выходную строку все операторы до первого встретившегося сим¬вола "(". Символы "(" и ")" уничтожают друг друга и в выходную строку не включаются.
5. Шаги 1-4 повторяются до тех пор, пока не будут просмотрены все символы входной строки. Затем оставшиеся в стеке операторы переносятся в выходную строку.