Termbaum

[n3cRo]

Hallo,
wir machen immoment in der Schule ein Projekt bei dem als Resultat ein Termbaum entstehen soll. Dieser basiert auf einem Binärbaum. Er soll nachher so aussehn das in jeder Wurzel ein Operator steht und in den Blättern jeweils die Operanden bzw. weitere Operatoren.
Wir haben quasi ein Hauptprogramm das die Klasse Binärbaum und die Klasse Parser hat. Der Parser soll den Term zerlegen und einen passenden Termbaum erzeugen (hierfür packt er die Operatoren/Operanden vom Typ Termbauminhalt in den Binärbaum). Später soll das Hauptprogramm den Termbaum noch durchlaufen und ein Ergebnis berechnen.

Mein Problem:
Wie parse ich den String richtig? (Rechenregeln müssen beachtet werden, der Parser muss nur +-*/ und ^ kennen)
Und wie baue ich anschließend den Termbaum richtig auf?

Ich finde einfach keinen vernünftigen Ansatz.
Danke für eure Hilfe

PS: Ich habe nichts gegen fertigen Code

[dizzy]

(M)Ein (fast) fertiger Parser der genau so arbeitet.

Er ist zwar etwas größer, da er auch sin() und Konsorten kann, und nicht nur "normale" reelle Zahlen kann, und unterstützt Variablen, aber im Prinzip ist er genau das, was du willst.



gruss,
dizzy

\\edit:

Schon wieder vergessen:
Herzlich wilkommen in der DP!

[n3cRo]

Hi,
irgendwie bin ich nicht in der Lage diesen komplexen Code zu abstrahieren und zu übertragen.
Kannst du mir nichmal prinzipiell erklären wie ich nen String parse und in nen Baum reinpacke?
Der Term wird nur aus +-*/^() und Ganzzahlen bestehen also keine E-funktionen etc.
Den Binärbaum den wir verwenden habe ich ja bereits als Anlage beigefügt.
Danke

[dizzy]

Also mit den Units von dir komme ich nicht so auf Anhieb klar. Das sind alles so ekelige "Schul-Bezeichner" - alles in Deutsch, und so übermäßig lang... igitt

Aber das Prinzip:
Du durchsuchst deinen String zeichenweise nach Operatoren wie '+'. Wenn du einen solchen gefunden hast, legst du einen Knoten im Baum an, der die Information entählt, dass die beiden Unterknoten zu addieren sind.
Jetzt schickst du den Teil des Strings links vom '+' und den Teil rechts vom '+' wieder in die selbe Prozedur (also rekursiv), und sobald du keinen Operator mehr findest, muss es sich um eine Zahl handeln. Für diese auch wieder einen Knoten (Blatt) erstellen, der die Zahl als Wert enthält. So dröselt sich Stück für Stück dein Baum zusammen.
Dass z.B. '*' vor '+' gerechnet wird, lässt sich ganz einfach dadurch realisieren, dass du als erstes den String nach dem Operator mit der schwächsten Bindung durchsuchst - also '+' oder '-'. Dann erst '*' und '/', und zuletzt '^'.

Ich hab meinen Parser mal um die Variablen, Unären Funktionen (sin(x)...), Klammernunterstützung und die komplexen Zahlen/Quaternionen beschnitten. Sieht jetzt deutlich handlicher aus

Delphi-Quellcode:

unit CQParser;

interface

uses SysUtils, Math;

type
  TOperation = (opAdd, opSub, opMul, opDiv, opPow, opConst);

// ******** classes for building the parsed formula as tree
  TRNode = class(TObject)
  private
    Fval: Double;
    Fop : TOperation;
  protected
    subNodes: array[0..1] of TRNode;
  public
    function Solve: double;
    constructor Create(val: Double); overload;
    constructor Create(op: TOperation); overload;
  end;

// ******** Main-Parser Class
  TCQParser = class(TObject)
  private
    FRootR: TRNode;
  protected
    procedure FlushTrees(var nd: TRNode);
    procedure TTR(s: string; var currentND: TRNode);
  public
    procedure Parse(formula: string);
    procedure Solve(var result: double);
    destructor Destroy; override;
  end;

implementation

(****************************** TRNode ****************************************)
constructor TRNode.Create(val: Double);
begin
  inherited Create;
  Fval := val;
  Fop := opConst;
end;

constructor TRNode.Create(op: TOperation);
begin
  inherited Create;
  Fop := op;
end;

function TRNode.Solve: double;
begin
  case Fop of
    opAdd   : result := subNodes[0].Solve + subNodes[1].Solve;
    opSub   : result := subNodes[0].Solve - subNodes[1].Solve;
    opMul   : result := subNodes[0].Solve * subNodes[1].Solve;
    opDiv   : result := subNodes[0].Solve / subNodes[1].Solve;
    opPow   : result := Power(subNodes[0].Solve, subNodes[1].Solve);
    else result := Fval;
  end;
end;


(************** Parser begin **********************************)
destructor TCQParser.Destroy;
begin
  FlushTrees(FRootR);
  inherited Destroy;
end;

procedure TCQParser.FlushTrees(var nd: TRNode);
begin
  if Assigned(nd) then
  begin
    FreeTree(nd.subNodes[0]);
    FreeTree(nd.subNodes[1]);
    FreeAndNil(nd);
  end;
end;

procedure TCQParser.Parse(formula: string);
begin
  FlushTrees(FRootR);
  FRootR := TRNode.Create;
  TTR(formula, FRootR);
end;

procedure TCQParser.Solve(var result: double);
begin
  result := FRootR.Solve;
end;


(********* Helperfunctions *******************************)
//// Diese Funktionen vereinfachen lediglich das Suchen im String,
//// und das Zerteilen an einem Operator.

// pos0 finds the first symbol "c" in "s"
function pos0(const c: char; const s: string): integer;
var k: Integer;
begin
  z := 0;
  for k:=length(s) downto 1 do
  begin
    if (s[k]=c) then
    begin
      result := k; // hit
      exit;
    end;
  end;
  result := 0; // nothing found
end;

function starting(const s: string; const c: char): string;
begin
  result := copy(s,1,pos0(c,s)-1);
end;

function copyFrom(const s: string; const i: integer): string;
begin
  result := copy(s,i,length(s)-i+1);
end;

function ending(const s: string; const c: char):string;
begin
  result := copyFrom(s,pos0(c,s)+1);
end;

(********* actual parsing procedure **********************)
procedure TCQParser.TTR(s: string; var currentND: TRNode);
begin
  // Leerzeichen entfernen
  s := trim(s);
  if s = '' then exit;
  //// '+' ist Operand schwächster Bindung -> wird als erster geprüft
  //// Wenn gefunden, dann die beiden Teilstrings um ihn herum WIEDER mit TTR parsen
  //// (und TTR bekommt den Knoten mit, in den er die gefundene Info schreiben soll)
  //// und einen Knoten anlegen, der '+'-Info enthält
  if pos0('+',s)>0 then
  begin
    currentND := TRNode.Create(opAdd);
    TTR(starting(s,'+'), currentND.subNodes[0]);
    TTR(ending(s,'+'),   currentND.subNodes[1]);
    exit;
  end else
  if pos0('-',s)>0 then
  begin
    currentND := TRNode.Create(opSub);
    TTR(starting(s,'-'), currentND.subNodes[0]);
    TTR(ending(s,'-'),   currentND.subNodes[1]);
    exit;
  end else
  if pos0('*',s)>0 then
  begin
    currentND := TRNode.Create(opMul);
    TTR(starting(s,'*'), currentND.subNodes[0]);
    TTR(ending(s,'*'),   currentND.subNodes[1]);
    exit;
  end else
  if pos0('/',s)>0 then
  begin
    currentND := TRNode.Create(opDiv);
    TTR(starting(s,'/'), currentND.subNodes[0]);
    TTR(ending(s,'/'),   currentND.subNodes[1]);
    exit;
  end else
  if pos0('^',s)>0 then
  begin
    currentND := TRNode.Create(opPow);
    TTR(starting(s,'^'), currentND.subNodes[0]);
    TTR(ending(s,'^'),   currentND.subNodes[1]);
    exit;
  end else
  //// Keinen Operator im String gefunden, also muss eine Zahl vorliegen. Knoten mit Zahl erstellen
  //// und Ende der Rekursion (kein erneuter Aufruf von TTR)
  begin
    currentND := TRNode.Create(StrToFloat(s));
    exit;
  end;
end;

end.

Ich geb mal keine uneingeschränke Funktionsgarantie, da ich das Teil im Notepad "beschnitten" hab. Aber das Prinzip stimmt alle Male
Was für eine Schule ist das, die so ein Thema behandelt!? Ist schon nicht mehr ganz so trivial! Ich wäre heilfroh gewesen, wenn wir sowas gemacht hätten. Aber es war bei uns schon ein Highlight, wenn man die Farbe des Formulars ändern konnte

Den obigen Code musst du nur noch so umbauen, dass er zu deiner Knotenklasse passt. Ich hoffe, dass ich dir etwas helfen konnte - und wenn noch Fragen sind... ich bin weg .


gruss,
dizzy

[n3cRo]

Danke Danke Danke,
verstanden hab ich es schonmal (:
Wir machen in Info immoment Datenstrukturen also Listen, Bäume etc.
Nur eine Frage wie bringe ich jetz sinnvoll Klammern mit in den Parser?

[dizzy]

Für die Klammern sind zweierlei Dinge nötig:

1) Die Funktion "pos0" muss erweitert werden, so dass sie nur noch Zeichen findet, die NICHT in Klammern stehen. Das sieht dann so aus:

Delphi-Quellcode:

function pos0(const c: char; const s: string): integer;
var k, z: Integer; //z := number of brackets
begin
  z := 0;
  for k:=length(s) downto 1 do
  begin
    if s[k]='(' then inc(z);
    if s[k]=')' then dec(z);
    if (z=0) and (s[k]=c) then
    begin
      result := k; // hit
      exit;
    end;
  end;
  result := 0; // nothing found
end;

Bei einer offenen Klammer wird z erhöht, bei einer geschlossenen erniedrigt. Erst wenn z=0 und das richtige Zeichen ("c") gefunden wurde, DANN ist der Rückgabewert >0 => Das geforderte Zeichen wurde am Index "result" im String gefunden, und steht nicht in Klammern.

2) In der Prozedur "TTR" must du noch auf Klammern prüfen, und bei Fund dann den Term zwischen den Klammern wieder in TTR schmeissen.

Delphi-Quellcode:

// Letzter Abschnitt von obigem Quellcode mit Klammererweiterung
.
.
.
 if pos0('^',s)>0 then
  begin
    currentND := TRNode.Create(opPow);
    TTR(starting(s,'^'), currentND.subNodes[0]);
    TTR(ending(s,'^'),   currentND.subNodes[1]);
    exit;
  end else
//// Der Teil für die Klammern beginnt hier...
  if (s>'') and (s[1]='(') then
  begin
    s:=copy(s,2,length(s)-2);
    TTR(s, currentND);
    exit;
  end else
//// ...und endet hier :)
  //// Keinen Operator im String gefunden, also muss eine Zahl vorliegen. Knoten mit Zahl erstellen
  //// und Ende der Rekursion (kein erneuter Aufruf von TTR)
  begin
    currentND := TRNode.Create(StrToFloat(s));
    exit;
  end;
end;

3) Hast du nen Glück, dass das z.Zt. mein aktivstes Freizeitprojekt ist, und deshalb da noch so drin stecke

4) Viel Erfolg, und gewöhn dich nicht zu sehr an (halb-) fertige Quelltexte. War mehr nen Wilkommensservice (Und weil ich so stolz bin, dass das Teil endlich läuft *g*) Sonst ist das eher weniger Gang und Gebe.

5) Viele Grüße, dizzy

[n3cRo]

Juhuuu,
ich habs geschafft
und nochmal Danke, dass ihr euch soviel Zeit genommen habt.
dankääää (: