Префиксная и постфиксная записи

В префиксной нотации каждый знак операции ставится перед своими операндами, а в постфиксной – после. В этом и состоит их основное отличие от обычной (инфиксной) записи, когда операция проставляется между операндами. Например, инфиксное выражение a+b в префиксной нотации примет вид +ab, а в постфиксной ab+.

(a+b)*(c+d)

в префиксной записи будет выглядеть

*+ab+cd

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

Получение постфиксного или префиксного представления возможно разными путями. В частности используется алгоритм стека, который в простейшем случае сведется к:

1. сохранению идентификатора, когда он встретится при чтении слева направо;

2. помещению в стек знака операции;

3. в момент встречи конца выражения выдача из стека знака операции, который находится на вершине.

Другой метод в получении постфиксного выражения из выражения, представленного в виде бинарного дерева. Например, выражение

(a+b)*c+d

представляется в виде бинарного дерева как на рисунке.

Чтобы получить постфиксное выражение используют порядок обхода, определенный Кнутом:

1. обход левого поддерева снизу:

2. обход правого поддерева снизу:

3. посещение корня.

что дает в результате

ab+c*d+