Народ, у меня такая проблемма:
У меня курсач в котором нужно составить прог-у чтобы она переводила инфиксную запись в постфиксную, но в задании есть такие условия:
1) исходное выражение описывается бинарным деревом;
2) для представления дерева использовать списки потомков реализованых в динамической памяти.
............

Впринципе саму прогу то я уже написал, вот только в ней какаято ошибка, причём не понятно почему (по моему представлению всё правильно, но прог-а не работает);

Сама ошибка как я понимаю, находится при удалении вершины.
Но вот как её исправить, я не знаю???

Если кто сможет помочь мне с этим, буду очень признателен!!!

Замечание: На вид здесь код большой но на самом деле основная судь начинается после слов "Начало алгоритма"...

Код:

Код

unit Polskay_Zapis; interface uses  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,  Dialogs, StdCtrls, Buttons, ExtCtrls; type  el_type=record            Name:string;            Num:integer;          end;  List=^cell;  cell=record          element:el_type;          Next:List;       end;  position=List;  TREE=record         LP,RP:array of List;    // Список потомков         Pred:array of el_type; // Элемент указывающий на потомков         Root:integer; // Корень дерева       end;  TForm1 = class(TForm)    Panel1: TPanel;    Panel2: TPanel;    BitBtn1: TBitBtn;    BitBtn2: TBitBtn;    BitBtn3: TBitBtn;    Edit1: TEdit;    Edit2: TEdit;    Label1: TLabel;    Label2: TLabel;    Memo1: TMemo;    SpeedButton1: TSpeedButton;    OpenDialog1: TOpenDialog;    procedure BitBtn3Click(Sender: TObject);    procedure BitBtn1Click(Sender: TObject);    procedure SpeedButton1Click(Sender: TObject);  private    { Private declarations }  public    { Public declarations }  end; var  Form1: TForm1;  T:TREE;    // Дерево  Prohod:boolean; //Прход по одному из циклов  s:string;  // Содержимое исходного фала  NTR:integer; //Временный корень поддерева(номер)  TR:string;   //(Временный корень поддерева(название)  TempStr:string;  i,j,k,n,m:integer;  Result:string; //Результат implementation {$R *.dfm} procedure TForm1.BitBtn3Click(Sender: TObject); begin  close; end; procedure TForm1.BitBtn1Click(Sender: TObject); var  stater:string; begin (******************* Проверка на наличие ошибок *******************************)  if edit1.Text='' then    begin      application.MessageBox('Путь к файлу не задан!!!','Error');      edit1.SetFocus;      exit    end;  if edit2.Text='' then    begin      application.MessageBox('Путь к файлу с результатом не задан!!!','Error');      edit2.SetFocus;      exit    end;  stater:=edit2.text;  if (stater[2]+stater[3]<>':\') or (stater[length(stater)-3]+stater[length(stater)-2]+stater[length(stater)-1]+stater[length(stater)]<>'.txt') then    begin      application.MessageBox('Ошибка при запуске пути выходного файла!!','Error');      edit2.SelectAll;      edit2.SetFocus;      exit    end; (******************* Запись дерева на основании содержимого в файле ***********)  n:=0; m:=1; //Счётчики вершин  i:=1;  s:=memo1.Text;  TempStr:='';  Repeat    if s[i]<>#$D then TempStr:=TempStr+s[i];  // Указатель на корень    i:=i+1;  Until s[i]=#$D;  t.Root:=StrToInt(TempStr);  i:=i+1;  k:=0;  //Ñ÷¸ò÷èê âåðøèí  Repeat    if (s[i]<>#$D) and (s[i]<>#$A) and (s[i]<>' ') then      begin        k:=k+1;        SetLength(T.Pred,k);        Setlength(T.LP,k);        Setlength(T.RP,k);        TempStr:='';        Repeat          if (s[i]<>' ') and (s[i]<>#$D) and (s[i]<>#$A) then TempStr:=TempStr+s[i];          i:=i+1;        Until (s[i]=' ') or (s[i]=#$D);        T.Pred[k-1].Name:=TempStr;        T.Pred[k-1].Num:=n;        n:=n+1;        i:=i+1;        if  (s[i]<>#$D) and (s[i]<>#$A) then          begin            new(T.LP[k-1]);            TempStr:='';            Repeat              if (s[i]<>' ') and (s[i]<>#$D) and (s[i]<>#$A) then TempStr:=TempStr+s[i];              i:=i+1;            Until (s[i]=' ') or (s[i]=#$D) and (s[i]<>#$A);            T.LP[k-1].element.name:=TempStr;            T.LP[k-1].element.num:=m;            m:=m+1;            if (s[i]<>#$D) and (s[i]<>#$A) then              begin                new(T.RP[k-1]);                TempStr:='';                Repeat                  if (s[i]<>' ') and (s[i]<>#$D) and (s[i]<>#$A) then TempStr:=TempStr+s[i];                  i:=i+1;                Until (s[i]=' ') or (s[i]=#$D) and (s[i]<>#$A);                T.RP[k-1].element.name:=TempStr;                T.RP[k-1].element.num:=m;                m:=m+1;              end;          end        else          begin            new(T.LP[k-1]);            new(T.RP[k-1]);            T.LP[k-1].Next:=nil;            T.RP[k-1].Next:=nil;          end;      end    else i:=i+1;   until i>length(s); (******************* Начало алгоритма *****************************************)  NTR:=T.Root-1;  //Присвоить первую корневую вершину  Repeat    Prohod:=false;    if (T.LP[NTR].Next <> nil) and not(Prohod) and (T.Pred[NTR].Name<>'') then      begin        Prohod:=true;        TR:=T.LP[NTR].element.Name;        NTR:=T.LP[NTR].element.Num;      end;    if (T.RP[NTR].Next<>nil) and not(Prohod) and (T.Pred[NTR].Name<>'') then      begin        Prohod:=true;        TR:=T.RP[NTR].element.Name;        NTR:=T.RP[NTR].element.Num;      end;      if (T.LP[NTR].Next=nil) and (T.RP[NTR].Next=nil) and not(Prohod) then        begin          Prohod:=true;          Result:=Result+TR+' ';          (*********************** Удаление вершины ***********************)           T.Pred[NTR].Name:='';          (************************ конец обработки ***********************)          NTR:=T.Root-1;  //Присвоить следующую корневую вершину        end;  Until k=0;  Result:=Result+TR+' ';     end; procedure TForm1.SpeedButton1Click(Sender: TObject); begin  if opendialog1.Execute then    memo1.Lines.LoadFromFile(opendialog1.FileName);  edit1.Clear;  edit1.Text:=opendialog1.FileName;  edit2.Clear;  edit2.SetFocus; end; end.

В чём заключается ошибка ?

Ну например, если есть дерево, дапустим из трёх вершин, где 1-ая вершин например корень,
2-ая -- левый потомок, а 3-ья правый потомок, то при выполнении программы в моём разделе
"(*** Начало алгоритма ***)", сначала выполнится проверка: если левый потомок присутствует то NTR:=номер этого потомка и Repeat, повторится, а так как у 2-ой вершины левого потомка нет, то выполнится третье условие, где эта вершина занесётся в Result, и должна будет удалится, но она при очередном проходе в поисках следующей вершины снова заносится в NTR и TR...
И где тут ошибка никак немогу понять...

Вопрос:

Код

1      / \     /   \    2     3   / \   / \  4   5 6   7 /    | 8     9     / \    10 11

Что в итоге должно получиться ? Какая строка ?

Потом, сам подумай, в твоём примере про 3 вершины:

Код

1 / \ 2   3

1) NTR = корень
2) в Repeat сработало первое условие, теперь:
NTR = левый потомок, TR = "1"
3) в Repeat сработало третье условие, теперь:
Result := "1 ", NTR = корень, имя вершины №2 = "" (удалена)
4) в Repeat сработало первое условие, теперь:
NTR = левый потомок, TR = "1"

Т.е. история повторяется...
Т.к. в условиях 1 и 2 Repeat'а проверяется Name текущей вершины, а не левого/правого потомка... (или что-то другое, но не то что нужно)
У тебя запутанные структуры... Тут сложно сориентироваться...
Попробуй такое условие:
if (T.LP[NTR].Next <> nil) and not(Prohod) and (T.Pred[T.LP[NTR].element.Num].Name<>'') then ...
Аналогично для второго условия...

Почему бы не сделать структуру дерева попроще, т.е. более понятную:

Код

type  PNode = ^TNode;  TNode = record     Name : string;     LP, RP : PNode;  end;

Корень дерева - нод, имеет два потомка (LP, RP), те в свою очередь то же имеют и т.д... Так проще было бы, имхо... Или у тебя какие-то дополнительные цели были при введении такой замудрёной системы ?

Цитата

Вопрос: Код    1   / \   /  \ 2  3 / \  / \ 4  5 6  7 /  | 8  9   / \ 10 11 Что в итоге должно получиться ? Какая строка ?

Извиняюсь, я забыл сказать, что обход дерева производится в порядке "LRT"(т.е. сначало просматривается левая вершина, потом правая и потом корень)

Ответ на вопрос: 8_4_10_11_9_5_2_6_7_3_1

Да кстате, спасибо PoSoL, что помог мне разобратся, покрайней мере в том где была ошибка, но у меня почемуто досих пор не работает прога до конца, я конечно исправил некотрую часть кода, но гдето что-то осталось нетак...

Код

... (******************* Начало алгоритма *********************************)  NTR:=T.Root-1;  Repeat    Prohod:=false;    if (T.LP[NTR].Next <> nil) and not(Prohod) and (T.Pred[T.LP[NTR].element.Num].Name<>'') then      begin        Prohod:=true;        TR:=T.LP[NTR].element.Name;        NTR:=T.LP[NTR].element.Num;      end;    if (T.RP[NTR].Next <> nil) and not(Prohod) and (T.Pred[T.RP[NTR].element.Num].Name<>'') then      begin        Prohod:=true;        TR:=T.RP[NTR].element.Name;        NTR:=T.RP[NTR].element.Num;      end;      if (T.LP[NTR].Next=nil) and (T.RP[NTR].Next=nil) and not(Prohod) then        begin          Prohod:=true;          Result:=Result+TR+' ';          (*********************** Удаление вершины ************************ )           T.Pred[NTR].Name:='';           for j:=0 to k-1 do            if T.LP[j].element.Num=NTR then              T.LP[j].Next:=Nil;           for j:=0 to k-1 do            if T.RP[j].element.Num=NTR then              T.RP[j].Next:=Nil;          (************************ Конец обработки *************************)          NTR:=T.Root-1;          TR:='';        end;  Until T.Pred[0].Name=''; ...

Замечание: Посол кстати ты предложил ещё один вариант дерева, но как понему что-либо сделать, ведь там многие вещи (например информация о предках и т.п.) отсутствует, но если ты знаешь как по нему можно-было бы сделать чё-нибудь, то пришли Пример...

Заранее спасибо!!! С уважением Zero

Трудно тут разобраться, так что лучше сразу предложу вот что:

Цитата(Zero @ 24.10.2004, 17:20)

Замечание: Посол кстати ты предложил ещё один вариант дерева, но как понему что-либо сделать, ведь там многие вещи (например информация о предках и т.п.) отсутствует, но если ты знаешь как по нему можно-было бы сделать чё-нибудь, то пришли Пример...

Мдя, забыл про предка...
Вот пример:

Код

type  PNode = ^TNode;  TNode = record    Name : string;    Parent, LR, PR : PNode;  end;   function MakeNode(const s, nam : string; ParentNode : PNode) : PNode; var  p0, p : integer;  line, nam1, nam2 : string; begin  if nam = '' then  begin    Result := nil;    Exit;  end;  New(Result);  Result.Name := nam;  Result.Parent := ParentNode;  Result.LR := nil;  Result.PR := nil;  p0 := Pos(#13+nam, s)+1;  if p0 = 0 then Exit;  p := PosEx(#13, s, p0);  line := Copy(s, p0, p-p0);  p := Pos(':', line);  Delete(line, 1, p);  p := Pos(',', line);  if p = 0 then p := Length(line)+1;  nam1 := Copy(line, 1, p-1);  Delete(line, 1, p);  nam2 := line;  Result.LR := MakeNode(s, nam1, Result);  Result.PR := MakeNode(s, nam2, Result); end; function MakeTree (s : string) : PNode; var  i : integer;  root : string; begin  repeat    i := Pos(#10, s);    if i=0 then Break;    Delete(s, i, 1);  until False;  if s[Length(s)] <> #13 then s := s + #13;  i := Pos(#13, s);  root := Copy(s, 1, i-1);  Delete(s, 1, i-1);  Result := MakeNode (s, root, nil); end; procedure FreeTree (Root : PNode); begin  if Root = nil then Exit;  FreeTree(Root.LR);  FreeTree(Root.PR);  Dispose(Root); end; function WalkTree (Root : PNode) : string; begin  if Root.LR <> nil then Result := WalkTree(Root.LR);  if Root.PR <> nil then Result := Result + ' ' + WalkTree(Root.PR);  if (Length(Result) > 0) and (Result[1] = ' ') then Delete(Result, 1, 1);  if Result <> '' then Result := Result + ' ';  Result := Result + Root.Name; end;

MakeTree - создаёт дерево из текста
FreeTree - освобождает дерево (память, занимаемую деревом)
WalkTree - обходит дерево в порядке LRT

Пример юзанья: занеси в Memo1 такой текст:

Код

1 1:2,3 2:4,5 3:6,7 4:8 5:9 9:10,11

(это то дерево, которое я рисовал для вопроса тебе)
Первая строка - имя вершины-корня
Далее идёт описание дерева:
<имя вершины>:<левый потомок>,<правый потомок>
PS: Имена - не обязательно цифровые

Далее на кнопку повесь такое:

Код

procedure TForm1.Button5Click(Sender: TObject); var Tree : PNode; begin  Tree := MakeTree(Memo1.Text); // создаём дерево  Caption := WalkTree(Tree); // обходим дерево  FreeTree (Tree); // освобождаем дерево end;

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

ИМХО, такая структура более понятна и с неё легче работать, особенно рекурсией...

Посол, извени что опять задаю тупые вопросы, но у меня функция PosEx, не работает, поэтому пока я разобрал смысл всего кода, то ...помоему там всё логично но хотелось бы всётаки его проверить...
Помоему как я понял функция PosEx определяет положение след. <Параметра1>, начиная с <Параметра3>, но за счёт того что ты использовал в процедуре Const s:string, то из этой сторки нельзя ничего удалять и соответственно чтобы нестандартно сделать функцию PosEx надо ещё не мало помучится, если ты знаешь как она сделана, то ни бог бы ты мне добавить этот код...

Ещё раз спасибо, за беспокойства!!! Zero.

Забыл, извини!
Ты правильно понял смысл PosEx, надо прописать в Uses модуль StrUtils:

Код

uses StrUtils, другие модули;

А так, в следующий раз, если где-то найдёшь код с функцией, которой у тебя нет, наведи на неё курсор, нажми F1, и если выведется справка по этой функции - то это стандартная дельфовая функция, и там указан, какой Unit надо использовать (прописать в uses)...

Цитата

Ещё раз спасибо, за беспокойства!!! Zero.

Не за что! Я тут для беспокойств и сижу

Вау, Клёво, Спасибо большое Посол!!! , ты даже не представляешь как ты мне помог!!!
Я уже несколько дней мучился с этой прого-й, а ты мне её круто упростил!!!

, захаживай почаще к нам!