Представление арифметических выражений в польской записи

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

Рассмотрим некоторое выражение a + b. Для него возможны три формы представления:

a + b - обычная, или инфиксная запись;

a b + - польская, или постфиксная запись;

+ a b - префиксная запись.

Наиболее удобной для использования в трансляторах является польская запись, основные свойства которой состоят в следующем.

1. Операнды в польской записи следуют в том же порядке, что и в инфиксной форме.

2. Операторы в польской записи следуют в том порядке (слева направо), в ко­тором они должны выполняться при вычислении выра­жений.

3. Операторы в польской записи располагаются непосредственно за своими операндами.

4. При использовании польской записи выражений не требуются скобки.

Необходимозаметить, что такой вид записи впервые применил польский логик Я. Лукашевич.

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

1) корень или верхняя точка (Т) дерева;

2) обход сверху левого (L) поддерева в порядке TLR;

3) обход сверху правого (R) поддерева в порядке TLR.

При получении постфиксной формы (польской записи) дерево просматривают снизу в порядке LRT:

1) обход снизу левого (L) поддерева в порядке LRT;

2) обход снизу правого (R) поддерева в порядке LRT;

3) корень дерева (Т).

Порядок просмотра можно пояснить на примере дерева, которое соответствует выражению a + b и приведено на рис. 2. Если на­чать с корня или верхней точки (T) этого дерева и напечатать "+", затем перейти к левой (L) нижней вершине и напечатать " a ", а далее перейти опять в корень, спуститься вправо (R) и напеча­тать " b ", то получим обход дерева сверху в порядке TLR. Пос­ледовательность напечатанных символов + ab будет префиксной формой выражения а + b.

Обход снизу рассмотрим на примере дерева, показанного на рис. 1. Для просмотра снизу левого (L) поддерева начинают с са­мой левой вершины, помеченной операндом а, проходят снизу под­дерево с корнем, соответствующим оператору " - ", и получают запись ab-.

Рис. 2. Варианты обхода дерева

Затем проходят поддерево с верхней точкой "*". В резуль­тате для левого поддерева получают следующий порядок прохождения вершин: ab-c *. Обход снизу правого (R) поддерева начинают с самой левой вершины этого поддерева, т.е. с вершины d. Затем проходят поддерево с корнем " ^ ". В итоге для правого поддерева получают запись def ^ /. Прохождение всего дерева снизу завер­шается в корневой вершине (T), помеченной оператором "+".

В ре­зультате получается последовательность операндов и операторов сле­дующего вида:

, (2)

которая представляет собой постфиксную форму (польскую запись) исходного выражения (1).

Прохождение этого же дерева сверху в порядке TLR позволяет получить пре­фиксную форму выражения (1):

.

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

Дата добавления: 2015-06-28