Поиск атома

Черновик.

pt found:=false;

0 1 while not found do begin

if not терм(pt^.left) then pt:=pt^.left

else if not терм(pt^.right) then

0 1 pt:=pt^.right else

found:=true;

0 1

Начинать каждый раз с корня неэффективно. Нужно искать ближайший к вычисленному атом. Всё прекрасно, если в дереве есть обратная ссылка на родителей. В нашем представлении их нет. Как вернуться к предыдущей вершине? Сохранять ссылки на предыдущую, а затем возвращаться к последней сохранённой.

Begin

pt:=root;

found:=false;

while not found do

begin

if not терм(pt^.left) then

begin

push(stack,pt);

pt:=pt^.left;

end;

else if not терм(pt^.right) then

begin

push(stack,pt);

pt:=pt^.right;

end

else found:=true;

pt^.info:=AtomVal(pt);

dispose(pt^.left);

dispose(pt^.right);

end;

pop(stack,pt);

end;

{Каждый раз начинаем с последней сохранённой вершины}

До начала цикла (инициализация стека):

create(stack);

push(stack,root);

Условия окончания цикла:

not терм(root);

not empty(stack);

Упражнения:

1) Решить задачу вычисления в случае, когда в дереве хранится ссылка на родителей.

2) То же самое, но вершины содержат только ссылки на родителей.

Дерево задаётся списком листьев.

Подзадача: вычислить значения атомов.

function AtomVal(pt:pNode):integer;

var arg1,arg2:integer;

begin

arg1:=TermVal(pt^.left);

arg2:=TermVal(pt^.right);

case pt^.info of

‘+’: AtomVal:=arg1+arg2;

‘*‘: AtomVal:=arg1*arg2;

‘/’: AtomVal:=arg1/arg2;

‘-‘: AtomVal:=arg1-arg2;

end;

end;

Вернёмся здесь к вопросу об определении типа Info. Сначала он char, затем должен содержать значения типа integer. Типом поля Info по нашему алгоритму должно служить объединение типов. Мы должны не только хранить в этом поле значеня разных типов, но и уметь определять, какого типа значение там хранится в текущий момент. Это помеченное объединение.

function TermVal(pt:pNode):integer;

begin

if {тип Info=integer} then TermVal:=pt^.info

else if pt^.info in [‘0’..’9’] then TermVal:=ord(pt^.info)-ord(0)

else TermVal:=VarVal[pt^.info];

Очевидный вариант определения типа tInfo – запись.

record

это integer:boolean;

CharInfo:char;

IntInfo:integer;

end;

Этот вариант хорош, если мы не хотим фактически уничтожать дерево. Условие “этоInteger=true” означает, что это выражение уже вычислено. Но если мы хотим уничтожить дерево, то такое определение типа неэффективно. Паскаль предлагает более эффективное решение.

Дата добавления: 2014-01-05