Помогите решить задачку.
По заданному выражению в префиксной форме надо построить бинарное дерево и вычислить его.
Вот нашел вариат задачи, которая на входе получает выражение в префиксной форме и выводит его в виде бинарного дерева.
http://forum.pascal.net.ru/index.php?showtopic=6208
Но прога обрабатыеат выражение как строку. Подскажите как написать какую-нибудь процедурку для вычисления этого выражения. Т.е. я ввожу например *+235, а на выходе получаю соответственно бинарное дерево и результат выражения. И объясните пожалуйста каким образом происходит вычисление выражения. Как строится дерево я вроде понял а вот как его вычислить не доходит.
Вот програ с линка который я написал. Можно ли ее доработать?
Заранее всем спасибо.
.
Uses Crt, Graph;
Type
TType = Char;
PTTree = ^TTree;
TTree = Record
Data: TType;
Left, Right: PTTree;
End;
procedure PrintTreeGraph(root: pttree);
var
global_root: pttree;
Procedure Build(Var root: PTTree;
Expr: String; Var Shift: Integer);
Begin
New(root);
Root^.Data := Expr[Shift];
Root^.Left := nil;
Root^.Right := nil;
If (Expr[Shift] in ['+','*','-','/']) Then Begin
Inc(Shift);
Build(Root^.Left, Expr, Shift);
Build(Root^.Right, Expr, Shift);
End
Else Inc(Shift)
End;
Const
i: integer = 1;
Var
s: string;
grDriver: integer;
grMode: integer;
ErrCode: Integer;
begin
global_root := nil;
writeln ('Vvedite virazenie v prefixnoy forme: ');
readln (s);
Build(global_root, s, i);
grDriver := Detect;
InitGraph(grDriver, grMode,'');
ErrCode := GraphResult;
if ErrCode <> grOk then begin
Writeln('Graphics error:', GraphErrorMsg(ErrCode)); Halt(100);
end;
PrintTreeGraph(global_root);
readln;
CloseGraph;
end
М | Пользуемся тегами CODE ! klem4 |
Основная идея: пишем функцию resultat, в которой производятся следующие действия:
if значение данного узла дерева ='+' , то resultat:=resultat(для правого поддерева)+resultat(для левого поддерева);
if значение данного узла дерева ='*' , то resultat:=resultat(для правого поддерева)*resultat(для левого поддерева); ...и т.д.
А когда нужно вычислить результат выражения по дереву, запускаем resultat(для корневого узла)
То есть если я тебя правильно понял вычисление узлов происходит примерно так
function resultat (root: pttree): integer;
begin
if root=nil then exit;
if root^.data = '+' then
resultat:=resultat(root^.left)+resultat(root^.right);
if root^.data = '-' then
resultat:=resultat(root^.left)-resultat(root^.right);
if root^.data = '*' then
resultat:=resultat(root^.left)*resultat(root^.right);
if root^.data = '/' then
resultat:=resultat(root^.left)/resultat(root^.right)
end
Если переменные строковые, то соответственно форматируем (процедура Val, см. паскалевскую справку)
Забыл самое главное - ещё добавить в функцию
if root=число then resultat:=это число;
Так не лучше будет?
function resultat (root: pttree): integer;
begin
if root=nil then exit;
case root^.data of
'+': resultat:=resultat(root^.left)+resultat(root^.right);
'-' : resultat:=resultat(root^.left)-resultat(root^.right);
'*' : resultat:=resultat(root^.left)*resultat(root^.right);
'/' : resultat:=resultat(root^.left)/resultat(root^.right);
else { Если НЕ знак, а цифра: }
begin
resultat := Ord(root^.data) - Ord('0'); { Если только одна цифра }
end;
end;
end;
function resultat (root: pttree): Real;
Для универсальности программки решил сделать так. Вообщем подразумевается, что на входе я получаю выражение с неизвестными значениями. (т.е. a,b,c...)
А в функции которая подсчитыевает результат я определяю эти значения (с помощью function Encode). Получается, что конвертировать ничего не надо. Вроде все замечательно. Но она почему то просит меня вводить по два раза каждое значение, т.е.
a=2
b=3
и снова
a=2
b=3
-=nix=-, приаттачь сюда свой PAS файл, чтобы можно было увидеть его полностью (кнопка "Ответить" -> выбираешь файл), тогда будет ясно, что у тебя в программе творится...
Извиняюсь сам накосячил. Все работает замечательно! Еще раз спасибо!
А PAS приттачу, хоть и коряво в некоторых местах написано (там где я своими руками лазил), но может кому-нибудь пригодится.
Прикрепленные файлы
B_TREE3.PAS ( 3.17 килобайт )
Кол-во скачиваний: 370