Построение бинарного дерева из формулы (Pascal)

[apostol584]

Я первый раз столкнулся с деревьями, помогите решить.

Формулу вида
<формула>::=<терминал>|(<формула><з нак><формула>)
<знак>::=+|-|*
<терминал>::=0|1|2|3|4|5|6|7|8|9 можно представить в виде двоичного дерева

1.вычислить значение дерева
2.по формуле из текстого файла f построить дерево
3.напечатать дерево в виде соответствующей формулы, определить высоту заданного дерева.

Мне бы код построения дерева, с остальным я разберусь.

[Sibedir]

Вообще, хотелось бы знать, соответствующий тип (узел) описан? Если да, то покажите. А то нужно с чего-то начать.

[apostol584]

type 
    tnode=^pnode;
    pnode=record
        info: char;
		left, right: tnode;
	end;
	
var
    formyla:string;
    root:tnode;

[Sibedir]

apostol584, извините, сразу не спросил.
Формат строки-формулы? В каком виде записыватся формула? Как обычно (8+3*5-1)? Или можно использовать упрощенные формы записи типа польской (-+8*351)?

-----------------------------------------------------------------
Короче, будем считать, что запись имеет обычный вид. Как создать дерево из польской записи, думаю и так понятно.

[apostol584]

Сообщение от Sibedir

apostol584, извините, сразу не спросил.
Формат строки-формулы? В каком виде записыватся формула? Как обычно (8+3*5-1)? Или можно использовать упрощенные формы записи типа польской (-+8*351)?

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

[Sibedir]

OK
___________________________________ ______________________________
Сразу позволю себе некоторую своевольность.

  PNode = ^TNode;
  TNode = record
    Data: Char;
    Parent: PNode;
    Left, Right: PNode;
  end;

Так будет немного помнемоничней
Да и Parent нам пригодится, чтоб не насиловать стек. Хотя можно было и без него

___________________________________ ______________________________
Ща сделаем, но это займет какое-то время. Потому-что доча

[apostol584]

огоромное спасибо.

[Sibedir]

Пока незачто
___________________________________ _________________________
70% готовности
- составлена блок-схема (фотку сделать не смог, не нашел SD-карту)
- набросал часть кода

program project1;

{$mode objfpc}{$H+}

uses
  {$IFDEF UNIX}{$IFDEF UseCThreads}
  cthreads,
  {$ENDIF}{$ENDIF}
  Classes, SysUtils, CustApp
  { you can add units after this };

type
  PNode = ^TNode;
  TNode = record
    Data: Char;
    Parent: PNode;
    Left, Right: PNode;
  end;

  TCharType = (chtTerm, chtZnak, chtSpace, chtNil, chtError);

procedure Error (Mes: String);
begin
  WriteLn (Mes);
  ReadLn;
  Halt;
end;

procedure ErrorInPosition (Pos: Integer);
begin
  Error ('Error in ' + IntToStr(Pos) + ' position');
end;

function CharType (const ch: Char): TCharType;
begin
  case ch of
    '0'..'9'         : Result := chtTerm ;
    '+', '-', '*'    : Result := chtZnak ;
    #9, #10, #13, ' ': Result := chtSpace;
    #0               : Result := chtNil  ;
  else
    Result := chtError;
  end;
end;

function ZnakVes (const ch: Char): Byte;
begin
  case ch of
    '+', '-': Result := 1;
    '*'     : Result := 2;
  else
    Error ('Invalid argument in ZnakVes (' + ch + ')');
  end;
end;

function NewNode (const ch: Char): PNode;
begin
  New (Result);
  with Result^ do begin
    Data   := ch;
    Parent := nil;
    Left   := nil;
    Right  := nil;
  end;
end;

function ReadBuf (buf: String): PNode;
var
  Cur, New: PNode;
  i, Count: Integer;
  ch: Char;
  Ojid: TCharType; // признак ожидания
begin
  // подготовка
  Cur := NewNode (#0);
  Ojid := chtTerm;
  Count := Length (buf);

  for i := 1 to Count do begin
    // читаем посимвольно
    ch := buf[i];
    case CharType (ch) of
      chtError, chtNil: ErrorInPosition (i);
    end;
  end;

  Result := Cur;
end;

function GetFormula (Root: PNode): String;
begin
  if Root = nil then
    Error ('Invalid argument in GetFormula (nil)')
  else begin
    Result := '';
  end;
end;

function CalcFormula (Root: PNode): Integer;
begin
  if Root = nil then
    Error ('Invalid argument in CalcFormula (nil)')
  else begin
    Result := 0;
  end;
end;

var
  Formyla: string;
  Root: PNode;

begin
  Formyla := '8 + 3*5*4 - 1 + 3*5'; //82
  Root := ReadBuf (Formyla);
  WriteLn (GetFormula (Root), ' = ', CalcFormula (Root));
end.

[apostol584]

Что делают эти модули cthreads, Classes, SysUtils, CustApp? Если я правильно понял, то программа написана да делфи или лазурусе.

[Sibedir]

Сообщение от apostol584

Что делают эти модули cthreads, Classes, SysUtils, CustApp?

Не важно. Все, что вам нужно, находится ниже

type

Сообщение от apostol584

Если я правильно понял, то программа написана да делфи или лазурусе.

На Лазарусе