Автор Герасимчик александр задал вопрос в разделе Другие языки и технологии
запись вырожения в постфиксной форме. и получил лучший ответ
Ответ от КАДУМ[активный]
ссылка
Преобразование из инфиксной нотации
Эдскер Дейкстра изобрёл алгоритм для преобразования выражений из инфиксной нотации в ОПН. Алгоритм получил название «сортировочная станция» , за сходство его операций с происходящим на железнодорожных сортировочных станциях. Инфиксная нотация — это форма математических записей, которую использует большинство людей (например, 3 + 4 или 3 + 4 * (2 - 1)). Как и алгоритм вычисления ОПН, алгоритм сортировочной станции основан на стеке. В преобразовании участвуют две текстовых переменных: входная и выходная строки. В процессе преобразования используется стек, хранящий ещё не добавленные к выходной строке операторы. Преобразующая программа читает входную строку последовательно символ за символом (символ — это не обязательно буква) , выполняет на каждом шаге некоторые действия в зависимости от того, какой символ был прочитан.
[править] Простой пример
Вход: 3 + 4
Добавим 3 к выходной строке (если прочитано число, то оно сразу добавляется к выходной строке) .
Помещаем + (или его Идентификатор) в стек операторов.
Добавим 4 к выходной строке.
Мы прочитали всё выражение, теперь выталкиваем все оставшиеся в стеке операторы в выходную строку. В нашем примере в стеке содержится только +.
Выходная строка: 3 4 +
В данном примере проявляются некоторые правила: все числа переносятся в выходную строку сразу после прочтения; когда выражение прочитано полностью, все оставшиеся в стеке операторы выталкиваются в выходную строку.
[править] Алгоритм
* Пока есть ещё символы для чтения:
* Читаем очередной символ.
* Если символ является числом, добавить его к выходной строке.
* Если символ является символом функции, помещаем его в стек.
* Если символ является разделителем аргументов функции (то есть, запятая) :
До тех пор, пока верхним элементом стека не станет открывающаяся скобка, выталкиваем элементы из стека в выходную строку. Если открывающаяся скобка не встретилась, это означает, что в выражении либо неверно поставлен разделитель, либо несогласованы скобки.
* Если символ является оператором, о1, тогда:
1) пока…
… (если оператор o1 ассоциированный, либо лево-ассоциированный) приоритет o1 меньше либо равен приоритету оператора, находящегося на вершине стека…
… (если оператор o1 право-ассоциированый) приоритет o1 меньше приоритета оператора, находящегося на вершине стека…
… выталкиваем верхние элементы стека c бо́льшим либо равным приоритетом в выходную строку;
2) помещаем оператор o1 в стек.
* Если символ является открывающейся скобкой, помещаем его в стек.
* Если символ является закрывающейся скобкой, выталкиваем элементы из стека в выходную строку до тех пор, пока на вершине стека не окажется открывающаяся скобка. При этом открывающаяся скобка удаляется из стека, но в выходную строку не добавляется. Если после этого шага на вершине стека оказывается символ функции, выталкиваем его в выходную строку. Если стек закончился раньше, чем мы встретили открывающуюся скобку, это означает, что в выражении несогласованы скобки.
* Когда входная строка закончилась, вытолкнуть все символы из стека в выходную строку. В стеке должны были остаться только символы операторов; если это не так, значит в выражении несогласованы скобки.