Сущность польской записи

Прямые методы трансляции

Из несинтаксических методов рассмотрим распространенный метод получения обратной польской записи.

Сущность польской записи

Способы записи выражений - прямая и обратная польские записи названы так в честь польского математика Яна Лукашевича.

Рассмотрим сущность обратной польской записи на примере:

Выражение a + b * c – d / (a + b) можно графически представить в виде дерева операций:

Здесь узлы – операции, а ветви – операнды. Левая ветвь – левый операнд, а правая – правый. В каждой ветви операциям, которые выполняются раньше, соответствуют нижележащие узлы. Корневая операция выполняется последней.

Если, начав с нижнего листа самой левой ветви, обойти все листья и узлы так, чтобы ветви рассматривались слева направо, а узел рассматривался только после обхода всех исходящих из него ветвей, как показано стрелками на рисунке, то получится обратная польская запись (ОПЗ): a b c * + d a b + / -.

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

procedure tree(v);

begin

if v.term then print(v.value)

else begin

tree(v.left)

tree(v.right)

print(v.value)

end;

end;

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

Таким образом, выражение можно вычислить в процессе однократного просмотра слева направо.

Если элемент – операнд, то переходим на следующий элемент. Если элемент – знак операции, то она выполняется над операндами, записанными слева от знака операции. Результат записывается вместо операндов и операции, которые вычеркиваются. Просмотр продолжается. В результате останется один элемент – значение выражения.

Аналогично можно записывать и вычислять булевские выражения.

Выражение a + b > - 5 and z - d = 1 + q ^ 2 представляется деревом:

Обход дерева дает ОПЗ a b + 5 из z d – 1 q 2 ­ + = and.

Иногда применяют прямую польскую запись (ППЗ) – префиксную запись.

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

Получается - + a * b c / d + a b.

В рекурсивной процедуре обхода дерева операций будет сначала выведен знак операции, а потом рассматриваются ветви-операнды.

print(v.value)

tree(v.left)

tree(v.right)

Выражения, записанные в ППЗ, вычисляются справа налево.