Алготитм 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.

Рис. 6.34.

Результат выражения = 14.000