Как работает алгоритм преобразования инфиксной записи в обратную польскую?

Алгоритм преобразования инфиксной записи в обратную польскую (также известный как «сортировочная станция») основан на стеке и разработан Эдсгером Дейкстрой. ru.wikipedia.org acm.petrsu.ru

Алгоритм рассматривает элементы выражения по очереди, слева направо. acm.petrsu.ru В преобразовании участвуют две текстовые переменные: входная и выходная строки. ru.wikipedia.org В процессе используется стек, который хранит ещё не добавленные к выходной строке операции. ru.wikipedia.org

Алгоритм работает по следующему алгоритму: kcdim.ru

1. Пока есть ещё символы для чтения: kcdim.ru

• Читают очередной символ. kcdim.ru
• Если символ является числом или постфиксной функцией, добавляют его к выходной строке. kcdim.ru
• Если символ является префиксной функцией, помещают его в стек. kcdim.ru
• Если символ является открывающей скобкой, помещают его в стек. kcdim.ru
• Если символ является закрывающей скобкой, то до тех пор, пока верхним элементом стека не станет открывающая скобка, выталкивают элементы из стека в выходную строку. kcdim.ru При этом открывающая скобка удаляется из стека, но в выходную строку не добавляется. kcdim.ru
• Если символ является бинарной операцией, то пока на вершине стека префиксная функция или операция на вершине стека приоритетнее или такого же уровня приоритета как бинарная операция, выталкивают верхний элемент стека в выходную строку, а бинарную операцию помещают в стек. kcdim.ru

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

Порядок операндов в выходной последовательности не отличается от порядка операндов в исходной последовательности, при этом в выходной последовательности отсутствуют скобки. otvet.mail.ru