Liste zu einem binären Baum umformen

[Alaitoc]

Tag zusammen,

ich habe eine Liste mit einem lexikanischen Scanner erstellt, in der Liste sind Objekte mit den Attributen Value und Token.
Jetzt will ich aber aus der Liste einen binären Baum erstellen, also parsen...

Also aus 3+4*3

wird:

Delphi-Quellcode:

    
. 
             +
           /   \
          3     *
              /   \
             4    3

Ich habe aber keine Ahnung wie genau ich mir den binären Baum erstellen soll...ich weiß wie ich ihn theorethisch durchsuchen kann..etc, aber beim erstellen hab ich einfach eine Denkblockade.

Schonmal Danke

MfG Alaitoc

[mkinzler]

Liste nach Trennzeichen Trennen in vor-Trennzeichen (linker Ast) und Rest ( rechter Ast)

Code:

Trennzeichen +

3 (linker Ast) 4*3 (rechter Ast) -> rekursiv trennen
               4 (linker Ast) 3 (rechter Ast)

[Alaitoc]

Das klappt auch wunderbar...am Ende hab ich dann halt alle Zahlen getrennt von den Zeichen...jedoch hab ich keine Ahnung wie ich daraus nen binären Baum baue...

[mkinzler]

Wie sieht den deine Baum-(Daten-)Struktur aus?

[Alaitoc]

Naja ich habe eine TTokenList, diese besteht aus TToken
TToken besteht aus Value(String) und Token(TTokens = (tkUnknown,tkInteger,tkFloat,tkVar, tkAdd,tkSub,tkDiv,tkMul,tkBrOpen,tkBrClose,tkPoten z))

Diese Items der TTokenList muss ich nun anhand der Token dem binären Baum zuweisen.
Als erstes kommen die + Zeichen, dann die - Zeichen , dann *, dann / , dann ^ etc…

Der binäre Baum soll wiederum aus Knoten bestehen, dieses beinhalten die Token und Left, Right die auf andere Knoten zeigen.

[mkinzler]

Ja aber für den Baum benötigst du ja eine Datenstruktur.

[Alaitoc]

Ein Binärbaum der aus Knoten besteht.
Diese bestehen aus ihrem eigenen Wert und nem Verweis auf die unteren Knoten.

z.b.

PTNode = ^TNode
Node = record
Token :TToken;
Left: PTNode;
Right: PTNode;
end;

[mkinzler]

Wie sieht die Liste genau aus (für das Beispiel oben)?

[Alaitoc]

Die Liste sieht z.B. so aus:

3+3*8

TokenList.Items[0].Value:='3';
TokenList.Items[0].Token:=tkInteger;
TokenList.Items[1].Value:='+';
TokenList.Items[1].Token:=tkAdd;
TokenList.Items[2].Value:='3';
TokenList.Items[2].Token:=tkInteger;
TokenList.Items[3].Value:='*';
TokenList.Items[3].Token:=tkMul;
TokenList.Items[4].Value:='8';
TokenList.Items[4].Token:=tkInteger;

Diese wird dann durchsucht mit ner eigenen Funktion die den Index ausgibt, falls das Token z.b. tkAdd vorhanden ist.
Dieses teilt dann die Liste in zwei seperate Listen, diese werden dann widerum mit der Funktion durchsucht, falls kein tkAdd vorhanden ist wird mit tkSub fortgefahren etc...
Bis halt jede Liste nur aus einem Item besteht.

[Medium]

Das ist doch schon fast fertig. Du müsstest dann nur noch wenn eine Liste zerteilt wird, je eine Hälfte an einen Baumknoten hängen der dann das Token bzw. den Wert enthält an dem zerteilt wurde. Das ganze rekursiv durchexerzieren bis nur noch 1-elementige Listen rumbaumeln, die du dann auch noch in einen Baumknoten ohne Nachfolger umwandeln könntest.

Es macht zudem Sinn entweder die Liste gleich mit den Baumstrukturen zu basteln (z.B. immer nur "links" anhängen), oder aber etwas OOP ins Spiel zu bringen in dem du etwas der Art nimmst:

Delphi-Quellcode:

type
  TElement = class
  private
    FValue: String;
    FToken: TToken;
  public
    property Value: String read FValue write FValue;
    property Token: String read FToken write FToken;
  end;

  TElementArray = array[0..1] of TElement;

  TElementListNode = class(TElement)
  private
    FNext: TElementListNode;
  public
    property Next: TElementListNode read FNext write FNext;
  end;

  TElementTreeNode = class(TElement)
  private
    FNext: TElementArray ;
  public
    property Next: TElementArray read FNext write FNext;
  end;

Die Verbindungen im Baumknoten könnte man zudem auch noch als Liste statt als Array ausführen, und man könnte Baum- und Listenknoten in eine weitere Klasse verpacken die dann diverse Operationen zur Verfügung stellt, etc. Da sind dann der Phantasie wenig Grenzen gesetzt wie weit man es treiben könnte wenn man wollte, wobei ein gemeinsamer Vorfahre in dieser Art schon einiges vereinfachen könnte, da man dann ja auf die Nutzdaten beider Knotenklassen über das selbe Interface heran kommt ohne große Spagate.