Помогите решить задачку.
По заданному выражению в префиксной форме надо построить бинарное дерево и вычислить его.

Вот нашел вариат задачи, которая на входе получает выражение в префиксной форме и выводит его в виде бинарного дерева.
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:=это число; 

Ну и удобнее поставить case вместо нескольких if

Так не лучше будет?

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;

В случае, если будешь делать более универсальную программу (для 2-х и более цифр в числе), конвертировать придется через Val

Кстати, у тебя в функции есть еще один подвох: операция "/" возвращает Real, а у тебя функция возвращает результат типа Integer, получишь ошибку... Лучше заголовок функции Resultat сделать таким:

function resultat (root: pttree): Real;

Ну, и деление на 0 не забывай проверять...

Для универсальности программки решил сделать так. Вообщем подразумевается, что на входе я получаю выражение с неизвестными значениями. (т.е. a,b,c...)
А в функции которая подсчитыевает результат я определяю эти значения (с помощью function Encode). Получается, что конвертировать ничего не надо. Вроде все замечательно. Но она почему то просит меня вводить по два раза каждое значение, т.е.
a=2
b=3
и снова
a=2
b=3

Помогите пожалуйста решить эту проблему.

Еще хочу спросить, можно ли записать в префиксной форме значения из нескольких символов, к примеру такое выражение 23+12.

И огромное спасибо за помощь volvo и atos! Вы мне очень сильно помогли!

-=nix=-, приаттачь сюда свой PAS файл, чтобы можно было увидеть его полностью (кнопка "Ответить" -> выбираешь файл), тогда будет ясно, что у тебя в программе творится...


чем не устраивает? Токены разделяй пробелами и все...

Извиняюсь сам накосячил. Все работает замечательно! Еще раз спасибо!
А PAS приттачу, хоть и коряво в некоторых местах написано (там где я своими руками лазил), но может кому-нибудь пригодится.