Обработка деревьев. Деревья выражений.

Несмотря на очень сложный вид (синтаксис), выражения обозначают функции и можно считать (если нужно привести – преобразовать), что выражения заданы в стандартном синтаксисе, в функциональной или префиксной нотации. Таким выражением будет элементарное выражение (терм) (обычно константа или переменная). Если e₁,…e_n – выражение, а f – знак операции, то строка вида f(e₁,…,e_n) – также выражение.

Деревом называется граф, состоящий либо из одной вершины, либо имеющий вид:



где e₁,…,e_n – деревья

Примеры:

ax²+bx+c

p:=1; for i:=1 to n do p:=p*a;

С обработкой выражений связаны три классические задачи программирования:

1. Синтаксический анализ: выяснить, является ли произвольный текст правильно построенным выражением.

2. Трансляция: по заданному выражению построить семантически эквивалентные выражения в другом синтаксисе (как правило более низкого уровня).

3. Выполнение: вычислить значение данного выражения.

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

Константы: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

Переменные: a, b, c, d, …, z

Знаки операций: + , - , * , /.

Выражение рассматривается в стандартной функциональной нотации.

ax²+bx+c – уже недопустимо

+*a*xx+*bxc

Семантика: арифметика целых чисел.

Задача по вычислению. Даны правильно построенное выражение и значения входящих в него переменных. Вычислить значение выражения.

ax+2b +*ax*2b

a1

x2

b3

АТОМ

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

left right

АТОМ

left<right

type tVariable=array[‘a’..’z’] of integer;

pComponent=^tComponent;

tComponent=record

info:char; {?}

left, right:pComponent; {Ссылки на левый и правый аргументы

(потомков)}

end;

function ExpVal(root:pComponent;variable:tVariable);

var pt:pComponent; {ссылка на следующий (next) вычисляемый атом}

begin

while {пока есть атомы} do

begin

{pt:= }

{Найти ссылку на первый атом, положить его в pt}

Вычисление атомов в лексикографическом порядке. (left<right)

{Сократить дерево, заменить атом на его значение}

pt^.info:=AtomVal(pt);

dispose(pt^.left);

dispose(pt^.right);

pt^.left:=nil;

pt^.right:=nil;

end;

end;

Конечно, можно не удалять вершины физически, а лишь помечать как удалённые.