Инфиксные, префиксные и постфиксные выражения¶

Преобразование инфиксного выражения в префиксное и постфиксное¶

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

Первой из рассматриваемых нами техник будет использование идеи полной расстановки скобок в выражении, рассмотренной нами ранее. Напомним, что A + B * C можно записать как (A + (B * C)), чтобы явно показать приоритет умножения перед сложением. Однако, при более близком рассмотрении вы увидите, что каждая пара скобок также отмечает начало и конец пары операндов с соответствующим оператором по середине.

Взгляните на правую скобку в подвыражении (B * C) выше. Если мы передвинем символ умножения с его позиции и удалим соответствующую левую скобку, получив B C *, то произойдёт конвертирование подвыражение в постфиксную нотацию. Если оператор сложения тоже передвинуть к соответствующей правой скобке и удалить связанную с ним левую скобку, то результатом станет полностью постфиксное выражение (см. рисунок 6).

Рисунок 6: Перемещение операторов вправо для постфиксной записи

Если мы сделаем тоже самое, но вместо передвижения символа на позицию к правой скобке, сдвинем его к левой, то получим префиксную нотацию (см. рисунок 7). Позиция пары скобок на самом деле является ключом к окончательной позиции заключённого между ними оператора.

Рисунок 7: Перемещение операторов влево для префиксной записи.

Таким образом, при преобразовании выражения (неважно, насколько сложного) в префиксную или постфиксную запись для установления порядка выполнения операций используется полная расстановка скобок. Затем находящийся внутри них оператор передвигается на крайнюю левую или крайнюю правую позицию - в зависимости от того, префиксную или постфиксную запись вы хотите получить.

Вот более сложное выражение: (A + B) * C - (D - E) * (F + G). Рисунок 8 демонстрирует его преобразование в постфиксный и префиксный виды.

Рисунок 8: Преобразование сложного выражения к префиксной и постфиксной записи.

Обобщённое преобразование из инфиксного в постфиксный вид¶

Нам необходимо разработать алгоритм преобразования любого инфиксного выражения в постфиксное. Для этого посмотрим ближе на сам процесс конвертирования.

Рассмотрим ещё раз выражение A + B * C. Как было показано выше, его постфиксным эквивалентом является A B C * +. Мы уже отмечали, что операнды A, B и C остаются на своих местах, а местоположение меняют только операторы. Ещё раз взглянем на операторы в инфиксном выражении. Первым при проходе слева направо нам попадётся +. Однако, в постфиксном выражении + находится в конце, так как следующий оператор, *, имеет приоритет над сложением. Порядок операторов в первоначальном выражении обратен результирующему постфиксному выражению.

В процессе обработки выражения операторы должны где-то храниться, пока не найден их соответствующий правый операнд. Также порядок этих сохраняемых операторов может быть обратным (из-за их приоритета), как в данном примере со сложением и умножением. Поскольку оператор сложения, появляющийся перед оператором умножения, имеет более низкий приоритет, то он должен появиться после использования последнего. Из-за такого обратного порядка имеет смысл рассмотреть использование стека для хранения операторов до тех пор, пока они не понадобятся.

Что насчёт (A + B) * C? Напомним его постфиксный эквивалент: A B + C *. Повторимся, что обрабатывая это инфиксное выражение слева направо, первым мы встретим +. В этом случае, когда мы увидим *, + уже будет помещён в результирующее выражение, поскольку имеет преимущество над * в силу использования скобок. Теперь можно приступить к рассмотрению работы алгоритма преобразования. Когда мы видим левую скобку, то сохраняем её как знак, что должен будет появиться другой оператор с высоким приоритетом. Он будет ожидать, пока не появится соответствующая правая скобка, чтобы отметить его местоположение (вспомните технику полной расстановки скобок). После появления правой скобки оператор выталкивается из стека.

Поскольку мы сканируем инфиксное выражение слева направо, то для хранения операторов будем использовать стек. Это предоставит нам обратный порядок, который был отмечен в первом примере. На вершине стека всегда будет последний сохранённый оператор. Когда бы мы не прочитали новый оператор, мы должны сравнить его по приоритету с операторами в стеке (если таковые имеются).

Предположим, что инфиксное выражение есть строка токенов, разделённых пробелами. Токенами операторов являются *, /, + и - вместе с правой и левой скобками, ( и ). Токены операндов - это однобуквенные идентификаторы A, B, C и так далее. Следующая последовательность шагов даст строку токенов в постфиксном порядке.

1. Создать пустой стек с названием opstack для хранения операторов. Создать пустой список для вывода.
2. Преобразовать инфиксную строку в список, используя строковый метод split.
3. Сканировать список токенов слева направо.
   • Если токен является операндом, то добавить его в конец выходного списка.
   • Если токен является левой скобкой, положить его в opstack.
   • Если токен является правой скобкой, то выталкивать элементы из opstack пока не будет найдена соответствующая левая скобка. Каждый оператор добавлять в конец выходного списка.
   • Если токен является оператором *, /, + или -, поместить его в opstack. Однако, перед этим вытолкнуть любой из операторов, уже находящихся в opstack, если он имеет больший или равный приоритет, и добавить его в результирующий список.

#. Когда входное выражение будет полностью обработано, проверить opstack. Любые операторы, всё ещё находящиеся в нём, следует вытолкнуть и добавить в конец итогового списка.

Рисунок 9 демонстрирует алгоритм преобразования, работающий над выражением A * B + C * D. Заметьте, что первый оператор * удаляется до того, как мы встречаем оператор +. Также + остаётся в стеке, когда появляется второй *, поскольку умножение имеет приоритет перед сложением. В конце инфиксного выражения из стека дважды происходит выталкивание, удаляя оба оператора и помещая + как последний элемент в результирующее постфиксное выражение.

Рисунок 9: Преобразование A * B + C * D в постфиксную запись

Чтобы закодировать алгоритм на Python, мы будем использовать словарь под именем prec для хранения значений приоритета операторов. Он связывает каждый оператор с целым числом, которые можно сравнивать с числами других операторов, как уровень приоритетности (для этого мы произвольно выбрали целые числа 3, 2 и 1). Левая скобка получит самое низкое значение. Таким образом, любой сравниваемый с ней оператор будет иметь приоритет выше и располагаться над ней. Строка 15 определяет, что операнды могут быть любыми символами в верхнем регистре или цифрами. Полная функция преобразования показана в ActiveCode 8.

Ниже показаны ещё несколько примеров выполнения этой функции.

>>> infixtopostfix("( A + B ) * ( C + D )")
'A B + C D + *'
>>> infixtopostfix("( A + B ) * C")
'A B + C *'
>>> infixtopostfix("A + B * C")
'A B C * +'
>>>

Постфиксные вычисления¶

В последнем примере использования стека мы рассмотрим вычисление выражения, которое уже находится в постфиксной форме. В этом случае структурой для решения задачи вновь выбран стек. Однако, поскольку вы сканируете постфиксное выражение, ждать своей очереди должны уже операнды, а не операторы, в противоположность алгоритму выше. Ещё один способ думать об этом решении: когда на входе обнаружится оператор, для вычисления будут использованы два самых последних операнда.

Чтобы разобраться в этом более детально, рассмотрим постфиксное выражение 4 5 6 * +. Сканируя его слева направо, вы прежде всего натолкнётесь на операнды 4 и 5. Что с ними делать неизвестно, пока не известен следующий символ. Помещение каждого из них в стек гарантирует их доступность на случай, если следующим появится оператор.

В нашем случае следующий символ - ещё один операнд. Так что мы, как и раньше, помещаем его в стек и проверяем следующий символ. Видим оператор *, что означает перемножение двух самых последних операндов. Сделав выталкивание из стека дважды, получим необходимые множители, а затем выполним умножение (в данном случае результатом будет 30).

Теперь можно обработать полученное значение, поместив его обратно в стек, чтобы оно могло использоваться в качестве операнда для последующих операторов в выражении. Когда будет обработан последний оператор, в стеке останется только одно значение. Выталкиваем его и возвращаем как результат выражения. Рисунок 10 демонстрирует содержание стека на протяжении всего процесса вычисления выражения из примера.

Рисунок 10: Содержание стека в процессе вычисления

На рисунке 11 показан несколько более сложный пример: 7 8 + 3 2 + /. Здесь есть два момента, которые стоит отметить. Первый: размер стека возрастает, уменьшается и вновь растёт в процессе вычисления подвыражений. Второй: обрабатывать оператор деления нужно очень внимательно. Напомним, что операнды в постфиксном выражении идут в их изначальном порядке, поскольку постфикс меняет только положение оператора. Когда операнды деления выталкиваются из стека, они находятся в обратной последовательности. Поскольку деление не коммутативный оператор (другими словами, \(15/5\) не то же самое, что \(5/15\)), мы должны быть уверены, что порядок операндов не изменился.

Рисунок 11: Более сложный пример вычисления

Предположим, что постфиксное выражение - это строка токенов, разделённых пробелами. Операторами являются *, /, + и -, а под операндами понимаются одноразрядные целые значения. На выходе будет целочисленный результат.

1. Создаём пустой стек под названием operandStack.
2. Преобразовываем строку в список, используя строковый метод split.
3. Сканируем список токенов слева направо.
   • Если токен является операндом, то преобразовываем его из строки в целое число и помещаем значение в operandStack.
   • Если токен является оператором *, /, + или -, то он нуждается в двух операндах. Производим выталкивание из operandStack дважды. Сначала вытолкнется второй операнд, а затем - первый. Выполняем арифметическую операцию и помещаем результат обратно в operandStack.
4. Когда входное выражение полностью обработано, его результат находится в стеке. Выталкиваем его из operandStack и возвращаем в качестве ответа.

Полностью функция для вычисления постфиксных выражений показана в ActiveCode 9. Для помощи с арифметикой определена вспомогательная функция doMath. Она принимает два операнда и оператор, после чего совершает надлежащую арифметическую операцию.

Важно отметить, что для обеих программ - постфиксного преобразования и постфиксного вычисления - мы предполагаем отсутствие ошибок во входном выражении. Используя эти программы, как точку отсчёта, вы можете легко увидеть, как в них могут быть включены определение ошибок и сообщение об этом. Мы оставляем это как упражнение в конце главы.