Infix, prefix and postfix form

Задача: разбор и вычисление арифметического выражения, представленного в виде строки.

Допустимые символы: основные бинарные операторы +, -, *, /; скобки (), цифры 0-9.

Для решения изначальной задачи потребуется два шага:

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

Основные идеи алгоритма сортировочной станции:

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

Определим операции и их приоритеты:

Приоритеты:

высокий: выражения, заключённые в скобки ( )

средний: * /

низкий: + −\

После того как постфиксная форма выражения сформирована, выражение может быть вычислено простым алгоритмом:

• Последовательно сканируем элементы из очереди с постфиксной записью