Почему работает алгоритм преобразования инфиксной записи в постфиксную
Существуют алгоритмы, короткие и простые по формулировке, но не очень лёгкие для понимания. Один из них — алгоритм преобразования выражения в инфиксной форме в постфиксную (она же обратная польская нотация), (он же алгоритм сортировочной станции).
Приведенные рассуждения помогут понять алгоритм и, при необходимости, восстановить по памяти и реализовать самостоятельно.
Суть обратной польской нотации
Напомню. Это важно для понимания алгоритма.
Это форма записи математических выражений, в которой операнды расположены перед знаками операций. Её преимущество в том, что выражение записанное таким образом можно вычислить за один проход по следующему алгоритму:
Заводим стек. Идем по выражению слева направо. Если встретили операнд, кладём в стек, если встретили операцию, достаём из стека операнд — это правый, достаём из стека операнд — это левый (да, в стеке выше находится правый операнд!) выполняем с ними операцию, результат кладём в стек, когда пройдём всё выражение в стеке будет лежать результат.
Пример:
Выражение в инфиксной форме »2 + 3×5 — 4»
Эквивалентное выражение в постфиксной форме »2 3 5 * + 4 -»
Вычисление выражения в постфиксной форме па шагам:
выражение: »2 3 5 * + 4 -» стек: []
выражение: »3 5 * + 4 -» стек: [2]
выражение: »5 * + 4 -» стек: [2, 3]
выражение: »* + 4 -» стек: [2, 3, 5]
выражение: »+ 4 -» стек: [2, 15]
выражение: »4 -» стек: [17]
выражение: »-» стек: [17, 4]
выражение: » стек: [13]
ответ 13
Описание алгоритма
Я рассматриваю алгоритм для выражений с левоассоциативными бинарными операторами (последовательность одинаковых операторов вычисляется слева направо. т.е. 1+2+3 вычисляется как (1+2) + 3), скобками.
Алгоритм преобразования из инфиксной формы в постфиксную:
Заводим стек, проходим по выражению слева направо.
если встретили операнд, записываем в ответ.
если встретили оператор — достаём из стека и записываем в ответ все операторы из стека пока они больше или равны текущему по приоритету или пока стек не опустеет или пока не встретили открывающую скобку в стеке; Кладём оператор в стек.
если встретили открывающую скобку кладём в стек.
если встретили закрывающую скобку записываем в ответ все операторы из стека пока не достанем из стека открывающую скобку.
Когда выражение закончилось, всё что осталось в стеке записываем в ответ.
Сам алгоритм довольно прост, но понять почему он работает не просто.
Объяснение
Попробуем придумать этот алгоритм по шагам начав с простых выражений постепенно усложняя их и модифицируя алгоритм. Начнём с простого примера.
»a + b» должно быть преобразовано в »a b +»
Операнды в ответе идут в том же порядке что и в исходной записи, переместился только оператор +. Придумываем такой алгоритм:
Записываем первый операнд в ответ, запоминаем куда-то оператор, записываем второй операнд, записываем оператор в ответ.
Усложняем пример.
«a + b — c» должно быть преобразовано в «a b + c -»
Мы работаем с левоассоциативными операторами поэтому мы хотим чтобы вначале выполняется +. Попробуем применить наш алгоритм. Действуем так: записываем a, + запоминаем, записываем b, записываем +, запоминаем -, записываем с, записываем -.
Пока работает. В общем виде:
если встретили операнд, то записываем в ответ.
если встретили оператор, то запоминаем, записываем в ответ после того как записали следующий операнд в ответ.
Добавим оператор с другим приоритетом.
«a + b * c» должно быть преобразовано в «a b c * +»
Для этого примера наш алгоритм не будет работать. После b рано записывать +, мы хотим, чтобы сначала выполнилось *, а значит нужно его раньше записать в ответ. Записывать + нужно когда далее будет равная по приоритету операция (т.к. мы хотим чтобы одинаковые по приоритету выполнялось слева направо: сначала то, что уже сохранено, потом то что позже встретили). В общем случае записывать запомненный оператор надо не после следующего операнда, а когда следующий оператор равен или меньше по приоритету. Или когда мы дошли до конца выражения. В итоге алгоритм принимает следующий вид:
если встретили операнд, то записываем с ответ.
если встретили оператор, то запоминаем, предварительно удалив запомненный ранее, если он есть и больше либо равен по приоритету.
Когда дошли до конца строки оператор записываем в ответ.
Так как мы теперь не записываем в ответ оператор сразу после следующего операнда, запоминать придётся более одного оператора. Также отметим, что добавлять операторы в ответ нужно в в порядке противоположном их запоминанию, поэтому хранить удобно в стеке.
Например
«a + b * c — d» должно быть преобразовано в «a b c * + d -»
После того как мы прошли с в стеке находятся +, * которые оба надо записать в ответ (вытолкнуть из стека) перед тем как добавить туда -. Получаем следующий алгоритм:
— если встретили операнд, то записываем в ответ.
— если встретили оператор, то сохраняем в стек, предварительно вытолкнув операторы из стека в ответ пока стек не пуст и оператор на вершине стека больше либо равен текущему по приоритету.
Когда дошли до конца строки все операторы из стека записываем в ответ.
Добавим скобки.
Выражение в скобках — это полноценное выражение которое после вычисления становится операндом, поэтому, когда мы встречаем открывающую скобку мы не должны выталкивать операторы из стека, сначала мы должны записать в ответ «операнд», т.е. все операторы и операнды в скобках.
Нам нужно запомнить место с которого начинается выражение в скобках — по сути отдельное выражение, для того, чтобы когда оно закончится (закрывающая скобка), знать какие операторы в стеке относятся к выражению в скобках, а какие были еще до скобок. Т.о. когда мы встречаем открывающую скобку то мы сохраняем её в стек как признак начала выражения в скобках.
При окончании выражения в скобках действуют правила окончания всего выражения: если встретили закрывающую скобку, то вытолкнуть все операторы до открывающей скобки (первой встретившейся, т.к. скобки могут быть вложенными).
В итоге получаем оригинальный алгоритм:
если встретили операнд, то записываем в ответ
если встретили оператор, то сохраняем в стек, предварительно вытолкнув операторы из стека в ответ пока стек не пуст и оператор на вершине стека больше либо равен текущему по приоритету или пока не встретим открывающую скобку
если встретили открывающую скобку, заносим её в стек
если встретили закрывающую скобку, операторы из стека записываем в ответ до открывающей скобки, открывающую удаляем из стека.
Когда дошли до конца строки все операторы из стека записываем в ответ.
