Модели и структуры данных



Описание программы:



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

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

  • 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.









Содержание    Назад    Вперед