Дерево как последовательность ветвей

Анализ алгоритма вычисления.

Дано выражение в текстовом файле. Вычислить значение выражения.

Дерево – естественная форма представления выражений, но неэффективно по расходу памяти. Если алгоритм сводится к последовательной обработке компонент некоторой последовательности в естественном порядке, не нужно держать в памяти всю последовательность. В алгоритме вычисления в каждый момент времени используются сведения лишь об одной ветке дерева (ссылка на которую хранится в стеке).

function NewNode(c:char):pNode;

var NewPt:pNode;

begin

new(NewPt);

NewPt^.info:=c;

NewPt^.left:=nil;

NewPt^.right:=nil;

NewNode:=NewPt;

end;

type

tInfo=record

case этоInteger:boolean of

true (IntInfo:integer);

false (CharInfo:char);

end;

end;

function ExpVal(var exp:text;VarVal: tVarVal):integer; {tVarVal» tVariable)}

var stack:tStack; {tStack of tInfo}

begin

create(stack); {Стек символов}

ReadChar(exp,f);

ReadChar(exp,x);

push(stack,f);

push(stack,x);

while not eof(exp) do

begin

{Пока не нашли атом, читай символы и складывай в стек}

pop(stack,x);

pop(stack,f); {/*+x1y2}

ReadChar(exp,c);

while not Atom(f,x,y) do

begin

push(stack,f);

push(stack,x);

push(stack,y);

pop(stack,x);

pop(stack,f);

ReadChar(exp,c);

end;

push(stack,AtomVal(f,x,y));

end;

pop(stack,x);

ExpVal:=x.IntInfo;

end;

Мы упоминали об относительности взгляда на структуры (деревья, графы) как на структуры данных и структуры управления. То, что раньше мы воспринимали как структуру данных (в первом алгоритме), стало трассой вычисления.

Задача синтаксического анализа.

На первый взгляд эта задача кажется совсем не похожей на задачу о вычислении. В реальности это практически та же задача.

Дана произвольная символьная последовательность. Выяснить, является ли она правильно построенным выражением.

/*+x1y2 – true

-*+x1y23 – false

Шаблоном текста c₁,…,c_n назовём текст _­­­c₁^|,…,c_n^|, где

‘t’, c_i – терм

c_i^|= ‘f’, c_i – знак операции

‘Æ’, c_i – чужой (посторонний) символ.

Шаблоном атома назовём строку c₁,c₂,c₃. Это либо строка f,t,t, где c₁=f, c₂=t, c₃=t, либо хотя бы один их них равен Æ.

Формальным вычислением назовём переход от шаблона атома c₁,c₂,c₃ к символу ‘t’ в случае ftt, либо к символу ‘Æ’ во втором случае. (?)

Последовательность есть выражение, если его можно преобразовать формальным вычислением к символу ‘t’.

procedure ReadMask(var exp:text;var m:char);

{Определение шаблонов атомов}

begin

if eof(exp) then m:=’Æ’

else

begin

read(exp,c);

if c in [‘+’, ’-‘, ’/’, ’*’] then m:=’f’

else if c in [‘a’..’z’]+[‘0’..’9’] then m:=’t’

else m:=’Æ’;

end;

end;

function CorrectExp(var exp:text):boolean;

begin

reset(exp);

create(stack);

ReadMask(exp,f);

push(stack,f);

b:=(f<>’Æ’) and (f =’t’) and not eof(exp);

ReadMask(exp,x);

push(stack,x);

b:=b and (x<>’Æ’);

while b and not eof(exp) do

begin

pop(stack,x);

pop(stack,f);

ReadMask(exp,y);

while not AtomMask(f,x,y) do{проверяем на атом}

begin

push(stack,f);

push(stack,x);

push(stack,y);

pop(stack,x);

pop(stack,f);

ReadMask(exp,y);

end;

result:=AtomMaskVal(f,x,y);{Вычисляем шаблон}

push(stack,result);

b:=result<>0;

end;

CorrectExp:=(x=’t’) and empty(stack);

end;

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