На вход подается глобальная переменная 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.