В качестве примера приложения бинарных деревьев сформулируем
алгоритм ведения древовидно-структурированной таблицы символов.
Основной критерий, которому должна удовлетворять программа
ведения таблицы символов, состоит в максимальной эффективности
поиска в этой таблицы. Это требование возникает на этапе компиля-
ции, когда осуществляется много ссылок на записи таблицы симво-
лов. Необходимо, чтобы над таблицей символов можно было бы прове-
рить две операции - включение записей в таблицу и поиск их в ней.
Причем, каждая из этих операций содержит операцию просмотра таб-
лицы.
Древовидное представление таблицы выбирают по двум причинам:
1. Записи символов по мере их возникновения равномерно расп-
ределяются в соответствии с лексикографическим порядком, то при
хранении записей в дереве в таком же порядке табличный просмотр
становится почти эквивалентен двоичному просмотру.
2. В древовидной структуре легко поддерживать лексикографи-
ческий порядок, т.к. при включении в нее новой записи необходимо
изменить лишь несколько указателей.
Для простоты предположим, что при ведении таблицы символов
используется достаточно развитая система записей, допускающая
символьные строки переменной длины.
Кроме того, предположим, что подпрограмма ведения таблицы
символов используется при создании дерева данного блока програм-
мы. Это предположение ведет к тому, что попытка повторного вклю-
чения записи вызывает ошибку. В глобальном контексте повторные
записи допустимы, если они соответствую разным уровням блочной
структуры программы.
В некотором смысле таблица символов представляет собой мно-
жество деревьев - по одному для каждого уровня блочной структуры
программы.
Вершины бинарного дерева таблицы символов имеют формат:
┌──────┬─────────┬──────┬──────┐
│ LPTR │ SYMBOLS │ INFO │ RPTR │
└──────┴─────────┴──────┴──────┘
SYMBOLS - поле символьной строки, задающей идентификатор или
имя переменной ( для обеспечения фиксированной длины описания
вершин здесь можно хранить не саму строку, а лишь ее описатель );
INFO - некоторое множество полей, содержащих дополнительно
информацию об этом идентификаторе, например его тип данных.
Новая вершина создается путем исполнения оператора P при
этом ее адрес запоминается в переменной P.
Еще предлагается, что перед любым исполнением программы ве-
дения таблицы символов на некотором чистом уровне блочной струк-
туры уже имеется соответствующая головная вершина дерева, в поле
SYMBOLS в которое занесено значение, лексикографически большее,
чем любой допустимый идентификатор. Эта вершина адресуется указа-
телем HEAD[n], где n означает номер уровня блочной структуры.
Т.е. предполагается, что при входе в блок осуществляется обраще-
ние к основной переменной, управляющей созданием головных вершин
деревьев.
Операции включения записи в таблицу и операция поиска в таб-
лице содержат значительное количество одинаковых действий ( нап-
ример, просмотр ), поэтому рассмотрим только алгоритм TABLE, а
различать включение или поиск по переменной FLAG. Если FLAG - ис-
тинно - то включение глобальной переменной, если - ложно - поиск.
DATA - содержит имя идентификатора и дополнительную информацию
для него.
Если включение новой записи было выполнено успешно, то FLAG
сохраняет свое первоначальное значение противоположное начально-
му, что указывает на ошибку, означающую, что искомый идентифика-
тор уже присутствует в таблице данного уровня и выполняемый алго-
ритм завершается. Если FLAG = ложь, то надо выполнить операцию
поиска записи. В этом случае переменная NAME содержит имя иденти-
фикатора, который необходимо найти, а значение переменной. При
успешном поиске переменная DATA устанавливается на поле INFO со-
ответствующее записи таблицы символов. FLAG сохраняет свое значе-
ние и осуществляет возврат к вызванной программе. При неудаче
операции поиска, FLAG меняет свое значение и выходит из алгорит-
ма. В этом случае основная программа должна осуществлять поиск
записи в таблице, более низких уровней. Деревья с головными вер-
шинами HEAD[n-1], HEAD[n-2] b т.д.
АЛГОТИТМ 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; { Эта программа вычисляет }
{математические выражения : *, /, +, -, ^. }
- 219 -
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.32.
Введите ваше выражение: Дерево выглядит так:
a+d*(e-3)^2
Введите значения: [+]
a= 2 /
d= 3 [a]/ [*]
e= 5 /
[d]/ [^]
/
[-]/ [2]
/
[e]/ [3]
Рис. 6.32.
Результат выражения = 14.000