АЛГОТИТМ TABLE.

На вход подается глобальная переменная n, идентифицирующая номер уровня текущего блока и глобальная переменная FLAG, задающая требуемую операцию. Описываемый алгоритм выполняет эту операцию над древовидной структурированной таблицей символов, локальной относительно блока уровня u. Параметры DATA и NAME используются для передачи данных между алгоритмом и от того больше или меньше значение NAME кода исследуемой записи таблицы, осуществляется установка указателя на левый или правый потолок данной вершины и возврат к шагу 2 для дальнейших сравнений. Поскольку дерево упорядочено таким образом, что код каждой вершины левого ( правого ) поддерева лексикографических меньше (больше), чем код корневой вершины, то попытка спуска по пустому дереву означает, что требуемая запись в таблице отсутствует; при этом определяется место, где данная запись расположена.

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

ОПИСАНИЕ ПРОГРАММЫ:

Последовательность решения задачи:

· 1) Ввод выражения;

· 2) Построение бинарного дерева из данного выражения;

· 3) Вычисление математического выражения;

· 4) Вывод дерева на экран;

· 5) Вывод результата на экран.

Процедуры программы:
Процедура Tree - преобразует математическое выражение в бинарное дерево. Процедура работает с помощью рекурсивного нисходящего обхода. Имеет подпроцедуру UnderTree. Подпроцедура UnderTree - специальная процедура. Создает поддеревья исходя из приоритета математической операции. Имеет подпроцедуру Skob. Подпроцедура Skob - учитывает скобки в математическом выражении. Процедура Calc - вычисляет математическое выражение. Процедура использует рекурсивный нисходящий обход. Процедура Symb - определяет в дереве где переменная или константа, и где знак операции. Эта процедура нужна для вычисления математического выражения. Процедура использует рекурсивный нисходящий обход. Процедура OutTree - выводит дерево на экран. Процедура использует рекурсивный нисходящий обход.

{===== Программный пример 6.17 ====== }

{$M 65500,0,100000}

Program MathExpr; { Эта программа вычисляет }

{математические выражения : *, /, +, -, ^. }

Uses CRT;

Type tr=^rec; {Тип дерево}

rec=record

pole:string; {Информационное поле }

sym:boolean; {Флаг символа }

zn:real; {Значение переменной }

rend:boolean; {Вспомогательный флаг}

l,r:tr; {Указатели на потомка}

end;

Var root,el : tr; {вершина и узлы дерева}

st : string; {вспомогательная переменная}

i,j : byte; { -------"-------}

x,y : integer; { координаты для вывода дерева}

g : byte; {вспомогательная переменная}

yn : char; { -------"-------}

code : integer; { для procedure VAL }

{Процедура Tree }

{Преобразование арифметического выражения в бинарное дерево }

{ Процедура использует рекурсивный нисходящий обход }

Procedure Tree(p:tr);

Procedure undertree(c:char); { создает поддеревья}

Procedure Skob; {процедура для учитывания скобок}

begin i:=i+1;

repeat

If p^.pole[i]='(' then Skob; i:=i+1;

until p^.pole[i]=')';

end; {End of Skob}

begin

for i:=1 to Length(p^.pole) do

begin if p^.pole[i]='('

then begin g:=i; Skob;

if (p^.pole[i+1]<>'+') and (p^.pole[i+1]<>'-')

and (p^.pole[i+1]<>'*') and (p^.pole[i+1]<>'/')

and (p^.pole[g-1]<>'*') and (p^.pole[g-1]<>'/')

and (p^.pole[g-1]<>'-') and (p^.pole[g-1]<>'+')

and (p^.pole[i+1]<>'^') and (p^.pole[g-1]<>'^')

then begin delete(p^.pole,i,1);

delete(p^.pole,1,1); i:=0;

end; end;

if p^.pole[i]=c then

begin New(p^.l); p^.l^.l:=nil;

p^.l^.r:=nil;

p^.l^.pole:=copy(p^.pole,1,i-1);

p^.l^.zn:=0; p^.l^.sym:=false;

New(p^.r); p^.r^.l:=nil;

p^.r^.r:=nil;

p^.r^.pole:=copy(p^.pole,i+1,ord(p^.pole[0]));

p^.r^.zn:=0; p^.r^.sym:=false;

i:=ord(p^.pole[0]); p^.pole:=c;

end; end;

end; {end of UnderTree}

begin

if p<>nil then

{Строятся поддеревья в зависимости от приоритета}

{арифметической операции }

begin UnderTree('+'); UnderTree('-');

UnderTree('*'); Undertree('/');

Undertree('^'); Tree(p^.l); Tree(p^.r);

end;

end; {End of Tree}

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

{Процедура использует рекурсивный нисходящий обход}

Procedure Calc(p:tr);

begin

if p<> nil then begin

if p^.l^.sym and p^.r^.sym then begin

case p^.pole[1] of

'+' : begin p^.zn:=p^.l^.zn+p^.r^.zn;

p^.sym:=true; end;

'-' : begin p^.zn:=p^.l^.zn-p^.r^.zn;

p^.sym:=true; end;

'*' : begin p^.zn:=p^.l^.zn*p^.r^.zn;

p^.sym:=true; end;

'/' : begin p^.zn:=p^.l^.zn/p^.r^.zn;

p^.sym:=true; end;

'^' : begin p^.zn:=EXP(p^.r^.zn*LN(p^.l^.zn));

p^.sym:=true; end;

end; {end of case} end;

Calc(p^.l); Calc(p^.r);

end;

end; {end of calc}

{Процедура определяет где в дереве переменная или значение,}

{и где знак операции. Использует рекурсивный нисходящий обход}

Procedure Symb(p:tr);

begin

if p<> nil then begin

if p^.pole[1] in ['a'..'z']

then begin p^.sym:=true; Write(p^.pole,'= ');

Readln(p^.zn); end;

if p^.pole[1] in ['0'..'9']

then begin p^.sym:=true;

VAL(p^.pole,p^.zn,code); end;

Symb(p^.l); Symb(p^.r); end;

end; {End of Symb}

{ Процедура выводит на экран полученное дерево }

{ Процедура использует рекурсивный нисходящий обход}

Procedure OutTree(pr:tr;f:byte);

begin

y:=y+2;

if pr<>nil then begin

If f=1 then begin x:=x-5; end;

if f=2 then begin x:=x+9; end;

GotoXY(X,Y);

{Если f=0, то выводится корневая вершина}

if f=0 then Writeln('[',pr^.pole,']');

{Если f=1, то - левое поддерево}

if f=1 then Writeln('[',pr^.pole,']/');

{Если f=2, то - правое поддерево}

if f=2 then Writeln('[',pr^.pole,']');

OutTree(pr^.l,1); OutTree(pr^.r,2);

end; y:=y-2;

end; {End of OutTree}

begin {Главная программа}

repeat

Window(1,1,80,25); x:=22; y:=0;

TextBackGround(7); TextColor(Blue); ClrScr;

{Ввод выражения, которое надо посчитать}

Writeln('Введите ваше выражение:');

GotoXY(40,4); Write('Используйте следующие операции:');

GotoXY(50,5); Write(' + , - , * , / , ^ ');

GotoXY(40,7); Write('Программа применяет деревья для');

GotoXY(40,8); Write('вычисления арифметического вы-');

GotoXY(40,9); Write('ражения.');

GotoXY(1,2); Readln(st);

{root Создается корневая вершина}

New(el); el^.l:=nil; el^.r:=nil; El^.pole:=st;

el^.zn:=0; el^.sym:=false; el^.rend:=false; root:=el;

{end of root}

Tree(root); {Создается дерево}

{Ввод значений переменных}

Writeln('Введите значения:'); Symb(root); Window(30,1,80,25);

TextBackGround(Blue); TextColor(White); ClrScr;

WriteLn('Дерево выглядит так:'); {Вывод дерева на экран}

OutTree(root,0);

repeat

if root^.l^.sym and root^.r^.sym

then begin Calc(root); root^.rend:=true; end

else calc(root);

until root^.rend;

Window(1,23,29,25); TextBackGround(Red);

TextColor(Green); ClrScr;

Writeln('Результат =',root^.zn:2:3); {Вывод результата }

Write('Еще?(y/n)'); readln(yn);

until yn='n';

end.

Результат работы программы представлен на рис 6.34.