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

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

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

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

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

Рисунок 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.

Ниже показаны ещё несколько примеров выполнения кода в оболочке Python.

>>> 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. Она принимает два операнда и оператор, после чего совершает надлежащую арифметическую операцию.

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