Mathematischen Ausruck als Binärbaum darstellen

[MrMooed]

Hallo DP,

Ich beschäftige mich zur Zeit mit einem Funktionsplotter. (bzw. erstmal mit dessen Rechenwerk :roll:)
Dazu habe ich mir überlegt, dass ich den Term zunächst als Binärbaum einlese, diesen mittels Postorder umstelle und dann ausrechne.
Alles bis auf das einlesen funktioniert soweit richtig :cry:
beim "postorder'n" kommt es immer zu einem Stack-Overflow, weshalb es wohl am einlesen liegen muss.

Delphi-Quellcode:

var Baum, tmp: TTree;
procedure TForm1.TermToTree(pTerm: String);
begin
  Baum := TTree.create;
  repeat
    case pTerm[1] of
      '+','-','*','/': begin
                         tmp := TTree.create;
                         tmp := Baum;  
                         Baum.setLeftTree(tmp);
                         Baum.setContent(TObject(Char(pTerm[1])));
                         Baum.setRightTree(TTree.create);
                         Baum := Baum.getRightTree;
                       end;
      '0'..'9': begin
                  Baum.setContent(TObject(String(Baum.getContent) + Char(pTerm[1])));
                end;
    end;
    delete(pTerm,1,1);
  until pTerm = '';
end;

Ich vermute, dass es an

Delphi-Quellcode:

tmp := Baum

liegt. Erstellt er damit keine neue Struktur, sondern setzt nur den zeiger von 'tmp' auf die Stelle wo 'Baum' liegt :?:
Wenn dem so ist, kann man das umgehen ?

//Edit: meine Klasse TTree sieht folgendermaßen aus:

Delphi-Quellcode:

TTree = class
    private
      content:   TObject;
      Open:      Boolean;
      root:      TTree;
      leftTree:  TTree;
      rightTree: TTree;
    public
      constructor create();
      procedure setContent(pContent: TObject);
      procedure setOpen(pOpen: Boolean);
      procedure setRoot(pRoot: TTree);
      procedure setLeftTree(pTree: TTree);
      procedure setRightTree(pTree: TTree);
      function getContent: TObject;
      function getRoot: TTree;
      function getLeftTree: TTree;
      function getRightTree: TTree;
      function haveChilds: Boolean;
      function isOpen: Boolean;
  end;

[Bjoerk]

Man kann nicht 2 erzeugte Instanzen gleichsetzen. Um die Felder zu kopieren brauchst du eine Procedere Assign.

Delphi-Quellcode:

procedure Assign(const Value: TTree);

[Jens01]

Guck Dir das mal an.

[MrMooed]

Zitat:

Zitat von Bjoerk (Beitrag 1209717)

Man kann nicht 2 erzeugte Instanzen gleichsetzen. Um die Felder zu kopieren brauchst du eine Procedere Assign.

Delphi-Quellcode:

procedure Assign(const Value: TTree);

in der procedure muss er dann den gesamten Baum durchlaufen und dessen Inhalt kopieren? Werde ich mal testen

Zitat:

Zitat von Jens01 (Beitrag 1209719)

Guck Dir das mal an.

Ahh.. da hatte unser Lehrer die alte Aufgabe her :-D, mit einem Stack habe ich schon herumexperimentiert und es klappt auch. Allerdings wollte ich das gerne auch mit einem Baum realisieren, da mir das einfacher zu interpretieren scheint (vor allem, wenn später noch Exp.-Funktionen und der gleichen hinzukommen sollen):?

[Jens01]

Zitat:

Zitat von MrMooed (Beitrag 1209729)

Allerdings wollte ich das gerne auch mit einem Baum realisieren, da mir das einfacher zu interpretieren scheint (vor allem, wenn später noch Exp.-Funktionen und der gleichen hinzukommen sollen):?

Glaube ich nicht. Du kannst Dir ja mal diesen fertigen Code angucken.

[Furtbichler]

Zitat:

Zitat von Jens01 (Beitrag 1209736)

Zitat:

Zitat von MrMooed (Beitrag 1209729)

Allerdings wollte ich das gerne auch mit einem Baum realisieren...

Glaube ich nicht...

Glaube ich schon, denn der Baum entspricht der syntaktischen Transformation in einem Parser (=> kontextfreie Grammatik). Das man das auch einfacher hinbekommen kann, steht außer Frage.

[MrMooed]

da bin ich wieder :-D

Habe sogar von Bäumen heute Nacht geträumt :pale: jedenfalls fiel mir die Lösung Heute Morgen dann plötlich ein :lol: Nach einigen Fehlschlägen und schusseligkeiten habe ich den Code etwas gekürzt und verschönert - aber das wichtigste er funktioniert (zur Zeit nur +,-,*,/ aber immerhin :) )

Falls ich Zeit habe und es irgendwen interessiert, kann ich das fertige Programm kommentieren/ erklären und hier im Software Bereich hochladen.

Die fertige TermToTree funktion sieht nun so aus:

Delphi-Quellcode:

function TMath.TermToTree(pTerm: String): TTree;
var
  Baum, tmp: TTree;
begin
  Baum := TTree.create;
  tmp := TTree.create;
  repeat
    case pTerm[1] of
      '0'..'9': Baum.setContent(Baum.getContent + pTerm[1]);
      else begin
             case pTerm[1] of
               '+','-' : begin
                           while not (Baum.getRoot = nil) do
                             Baum := Baum.getRoot;
                           tmp := TTree.create;
                         end;
               '*','/' : begin
                          if not (Baum.getRoot = nil)
                            then
                              begin
                                tmp := Baum.getRoot;
                                tmp.setRightTree(TTree.create);
                                tmp := tmp.getRightTree;
                            end;
                         end
               else showmessage('Ungültige Eingabe!');
             end;
             tmp.setContent(pTerm[1]);
             tmp.setLeftTree(Baum);
             tmp.setRightTree(TTree.create);
             Baum := tmp.getRightTree;
           end;
    end;
    delete(pTerm,1,1);
  until pTerm = '';

  //hocharbeiten bis zur wurzel und zurückgeben
  while not (Baum.getRoot = nil) do
    Baum := Baum.getRoot;
  result := Baum;
end;

Wenn jemand meine Gedanken nachvollziehen kann und optimierungsvorschläge hat - immer her damit :stupid:

[Mavarik]

Zitat:

Zitat von MrMooed (Beitrag 1209840)

da bin ich wieder :-D

Wenn jemand meine Gedanken nachvollziehen kann und optimierungsvorschläge hat - immer her damit :stupid:

Schau Dir mal den Link von Jens01 an... UPN ftw...

Mavarik

[Jens01]

Was bei Mathparsern immer vergessen wird, ist das Testen. Informier Dich doch mal über Unittesting z.B. mit DUnit. Damit kannst Du auch noch den Lehrer beeindrucken!:wink:

[Bjoerk]

Zitat:

Zitat von MrMooed (Beitrag 1209840)

da bin ich wieder :-D aber das wichtigste er funktioniert (zur Zeit nur +,-,*,/ aber immerhin :) )

Sehr schön. Kompliment. Vielleicht noch kurz zur Reihenfolge der Auswertung:

Klammern,
Functions (sin / cos ect.),
Power,
Mult / Div,
Plus / Minus.

Um zwei leidige Themen wirst du dich im weiteren Verlauf auch noch kümmern müssen,
Exponentialdarstellung (z.B. 2.1E-8)
und unäres Minus z.B. -3^-2.

Ist aber alles kein Hexenwerk. Du schaffst das!

Gruß
Thomas