Алгоритмы обработки выражений.

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

1) либо термом, т.е.

a) либо именем константы вида b₁… b_n.c₁… c_m , где

(n>0) & (m>0) & " iÎ[1,n](b_iÎ ['0','9']) & " jÎ[1,m](c_jÎ ['0','9'])

b) либо именем переменной вида d₁… d_k, где

(k>0) & (d₁Î ['a','z']) & " iÎ[2,k](d_iÎ ['0','9']È['a','z'])

2) либо строкой вида (E₁)f(E₂), где E₁,E₂ - выражения, а f - один из знаков +,-,*,/

Аналогично определяются выражения в префиксной f(E₁)(E₂), и постфиксной (E₁)(E₂)f формах.

Определим также дерево выражения E как дерево над базовым типом string, состоящее из единственной вершины, содержащей Е, если Е - терм или же дерево вида

если Е - выражение вида (E₁)f(E₂).

Аналогично определяются деревья выражений в префиксной и постфиксной формах. Ясно, что вид дерева не зависит от синтаксиса/структуры сложного выражения. В чем и заключается их прелесть. Минус – больший расход памяти, по сравнению в линейной, строковой форме.

Как перейти от представления выражения деревом к линейной - инфиксной, префиксной и постфиксной форме? Ответ ищи в разных порядках обхода дерева в "Нелинейные типы данных".

Типом выражения E (и, соответственно, вершины, его содержащей) будем называть cимвол-метку 't', если Е - терм, и символ 'f', если Е - выражение, содержащее знак операции.

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

Строго говоря, для решения задачи мы должны также зафиксировать семантику выражений - что же они на самом деле обозначают? Ясно, что по умолчанию подразумевается традиционная арифметика вещественных чисел.

Для того, чтобы кратко и ясно представить основную идею алгоритма как сведение вычисления сложного выражения к вычислению элементарных выражений или атомов (содержащих, по определению, единственный знак операции), будем предполагать, что значения термов (констант и переменных) уже найдены (как это сделать - см. "Задачи текстовой обработки,3") и сохранены в самом дереве.

type

pNode=^tNode;

tNode= record

Name:string;

Val:integer;

left,right:pNode;

end;

Очевидно, это не очень экономное решение в смысле расхода памяти - для двух термов с одинаковым значением мы сохраняем значение дважды, а остальные (содержащие знаки операций) вершины вообще изначально не имеют значения. Обычно значения термов и промежуточные результаты сохраняют во внешних по отношению к дереву таблицах.

{вычисление элементарного выражения}

function AtomVal(root:pExpr):T;

begin

with root^ do

case Name of

'+': AtomVal:=left^.Val+right^.Val;

'-': AtomVal:=left^.Val-right^.Val;

'*': AtomVal:=left^.Val*right^.Val;

'/': AtomVal:=left^.Val/right^.Val;

{для простоты, опускаем обработку исключения - деления на 0}

end; end;

{выяснение типа вершины}

function NodeType(pt:pNode):char;

begin

with pt^ do

if (right=nil) and (left=nil)

then NodeType='t'

else NodeType='f'

end;

{поиск атома, лежащего ниже данной вершины}

{идея: вычисление $-свойства found:=$ ptÎpNode (pt¹nil & pt^.left¹nil & pt^.right¹nil) }

{см."Вычисление свойств"}

{предусловие: вершина pt содержит знак операции, NodeType(pt)='f'}

procedure FindAtom(var pt:pNode; var stack: pStack);

var found:Boolean;

begin

with pt^ do

begin

found:=false;

while not found do

begin

if NodeType(left) ='f'

then begin push(pt,stack); pt:=left end

else if NodeType(right)='f'

then begin push(pt,stack); pt:=right end

else

{ это терм » NodeType(pt)='f' & NodeType(left) ='t' & NodeType(right)='t'}

found:=true

end;

end;

{предусловие - дерево не вырождено, все термы уже означены}

function ExpVal(root:pExpr):T;

var

stack:pStack;

{вспомогательный стек ссылок pNode на еще не вычисленные знаки операций}

{реализацию см. "Абстрактные линейные типы данных"}

found:Boolean; {есть еще атомы?}

RootType,LeftType,RightType:char; {{'t','f')}

begin

Create(stack);

UpperType:=NodeType1(root);

if UpperType='f' then

push(stack,root);

while not empty(stack) {= есть невычисленные операции} do

begin

{следующий поиск начинаем c вершины, ближайшей к вычисленному атому}

pop(stack,pt); FindAtom(pt,stack);

{Вычисли значение атомарного выражения}

pt^.val:= AtomValue(pt);

{Сократи дерево}

destroy(pt^.right); pt^.right:=nil;

destroy(pt^.left); pt^.left:=nil;

end;

{Дерево состоит из одной вершины}

ExpVal:=root^.val;

end;

Замечание. Побочным (и не очень желательным) эффектом простоты нашего алгоритма является уничтожение самого дерева. В реальности, мы можем не уничтожать вычисленные термы, а лишь помечать их как уже вычисленные.

Задача. Синтаксический анализ выражения, представленного деревом. Проверить, является ли произвольное бинарное символьное дерево деревом выражения.

Задача синтаксического анализа очевидно распадается на анализ 1) термов и 2) сложных выражений. В данном случае, анализ термов прост и напрямую сводиться к задаче поиска (см. "Поиск"). Центральная идея: свести задачу анализа сложного выражения к задаче вычисления.

1) Анализ термов.

type tSetOfChar=set of char;

{Поиск позиции "исключения" - первого символа в подстроке s[start,finish], не принадлежащего множеству alphabet }

procedure FindException

(s:string; start,finish:Cardinal; alphabet:tSetOfChar; position:Cardinal; found:boolean);

{идея: проверка свойства found=$ positionÎ [start,end] (s[position] Ï alphabet)}

{см."Вычисление свойств" и "Поиск"}

begin

found:=false; position:=start;

while (position<=finish) and (not found) do

if s[position] in alphabet then inc(position) else found:=true;

end; { function FindException }

{проверка имени константы}

function ConstantName(s:string):boolean;

var

position, {позиция "исключения" - см. procedure FindException }

len:Cardinal; {длина выражения s}

found:boolean; {"исключение" найдено}

begin

len:=Length(s); ConstantName:=false;

FindException(s,1,len,['0'..'9'],position,found);

if (position=1) or (position=len) or (not found)

then {нет обязательной внутренней не-цифры} exit; {завершаем}

if s[position]<>'.'

then {эта не-цифра - не точка} exit; {завершаем}

{есть ли не-цифры после точки?}

FindException(s,position+1,len,['0'..'9'],position,found);

ConstantName:=not found

end;

{проверка имени переменной - еще проще}

function VariableName(s:string):boolean;

var

position, {позиция "исключения" - см. procedure FindException }

len:Cardinal; {длина выражения s}

found:boolean; {"исключение" найдено}

begin

len:=Length(s); VariableName:=false;

if len=0 then exit;

if not (s[1] in ['a'..'z']) then exit;

FindException(s,2,len,['0'..'9']+['a'..'z'],position,found);

VariableName:=not found

end;

2) Анализ (сложных) выражений.

Определим понятие расширенного (или просто р-) выражения как строки вида (E₁)F(E₂), где E₁,E₂ - произвольные, в том числе пустые строки, а F - произвольная непустая строка. Мотивация - любому невырожденному дереву однозначно сопоставляется некоторое р-выражение.

Расширим также понятие типа р-выражения за счет добавления "неопределенного" значения 'Æ' : если р-выражение не имеет типа 'f' или 't', то оно имеет тип 'Æ'. Формальным вычислением р-выражения назовем операцию Reduce (сократить, англ):

ì терм 'x', если Тип(E₁)=Тип(E₂)='t' и Тип(F)='f'

Reduce((E₁)F(E₂))= í

î 'Æ', в противном случае

(смысл прост - результатом вычисления правильного выражения является терм, а результат вычисления неправильного выражения не определен)

Идея алгоритма: Выражение правильно » тип результата формального вычисления = терм.

{расширенный тип вершины}

function ExtentedNodeType(pt:pNode):char;

var len:Cardinal; {длина строки}

begin

{теперь не уверены, что "листья" дерева - это термы!}

ExtendedNodeType:='Æ';

if pt=nil { тип пустого слова неопределен}

then exit; {= завершить определение значения функции }

with pt^ do

begin

len:=Length(name);

if len=0 then exit;

if (Len=1) and (name[1] in ['+','-','*','/']) and (left<>nil) and (right<>nil)

then begin ExtendedNodeType:='f'; exit end;

if (left=nil) and (right=nil) and

(ConstantName(pt^.name) or VariableName(pt^.name)

then ExtentedNodeType:='t'

end; {with}

end; { function ExtentedNodeType }

{теперь не уверены, что найдутся правильные атомы!}

{но, в таком случае, обязательно найдется не правильный }

{см. определение ниже в теле процедуры}

procedure FindExtendedAtom(var pt:pNode; var stack: pStack);

var found:Boolean;

begin

with pt^ do

begin

found:=false;

while not found do

begin

UpperType=NodeType(pt);

LeftType= NodeType(left);

RightType=NodeType(right);

if (UpperType<>'f') or (LeftType='Æ') or (RightType='Æ')

then

{дальше искать нечего, формально считаем - найден "не правильный" атом}

found:=true

else if LeftType='f'

then begin push(pt,stack); pt:=pt^.left end

else if RightType='f'

then begin push(pt,stack); pt:=pt^.right end

else {UpperType='f' & LeftType='t' & RightType='t'}

{ » найден правильный атом }

found:=true

end; {while}

end; {with }

end; { procedure FindAtom }

{формальное вычисление расширенного элементарного выражения}

function ExtendedAtomVal(root:pExpr):string;

begin

with root^ do

if (ExtendedNodeType(root)='f') and

(ExtendedNodeType(left)='t') and

(ExtendedNodeType(right)='t') {корректный атом}

then ExtendedAtomVal:='x' {сгодиться любой терм!}

else ExtendedAtomVal:='Æ';

end;

function ExpressionCorrect(root:pExpr):boolean;

begin

result:=true;

create(stack);

RootType:=ExtendedNodeType(root);

case RootType of

'Æ': result:=false;

'f': push(stack,root);

end;

while (not empty(stack)) and result do

begin

pop(stack,pt);

FindExtendedAtom(pt,stack);

{Формальное "вычисление"}

pt^.Name:=ExtendedAtomValue(pt);

if NodeType(pt)='Æ'

{если результат элементарного вычисления неопределен}

then Result:=false {то результат всего вычисления - и подавно}

else

begin {Сократи дерево}

destroy(pt^.right);

pt^.right:=nil;

destroy(pt^.left);

pt^.left:=nil;

end; {if}

end; {while}

Result:=(NodeType(root)='t')

end;