Autor Beitrag
n3cRo
Hält's aus hier
Beiträge: 3



BeitragVerfasst: So 30.05.04 02:10 
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



Die Binärbaumklasse:
ausblenden volle Höhe Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
{*******************************************************************************

 Dokumentation der Klasse "Binaerbaum"
 
 

 Klassenname: Binaerbaum
 Oberklasse:  keine

 Beschreibung: Beliebige Objekte können in der Datenstruktur Binärbaum verwaltet
 werden. Ein Binärbaum ist entweder leer oder er hat eine Wurzel und kennt einen
 rechten und einen linken Teilbaum. Die Teilbäume sind disjunkt, d.h. sie haben
 keine gemeinsamen Knoten.

 Bezugsklassen: tObject

 *******************************************************************************}


unit mBinaerbaum;

interface
  type Binaerbaum = class
    kenntInhalt: TObject;
    kenntLinkenNachfolger, kenntRechtenNachfolger: Binaerbaum;
    constructor init;overload;
    //nachher:  Ein leerer Baum existiert
    constructor init(pInhalt:TObject);overload;
    //nachher:  Der Binärbaum existiert und hat eine Wurzel mit dem übergebenen
    //          Inhalt und zwei leeren Teilbäumen
    constructor init(pInhalt:TObject;pLinkerBaum, pRechterBaum:Binaerbaum);overload;
    //nachher:  Der Binärbaum existiert hat eine Wurzel mit dem übergebenen
    //          Inhalt und den übergebenen Teilbäumen
    function neuerLeererBaum:Binaerbaum;virtual;
    //nachher:  Diese Anfrage liefert einen leeren Binaerbaum. Muss in
    //          Unterklassen überschrieben werden
    procedure ueberschreibeWurzel(pInhalt:TObject); virtual;
    //nachher:  Die Wurzel hat das übergebene Objekt als Inhalt, ein eventuell
    //          vorhandener Inhalt wird überschrieben
    procedure haengeRechtsAn(pBaum:Binaerbaum);
    //vorher:    Der Binärbaum ist nicht leer
    //nachher:  Die Wurzel hat den übergebenen Baum als rechtenTeilbaum
    procedure haengeLinksAn(pBaum:Binaerbaum);
    //vorher:    Der Binärbaum ist nicht leer
    //nachher:  Die Wurzel hat den übergebenen Baum als linkenTeilbaum
    function wurzelInhalt:TObject;
    //vorher:    Der Binärbaum ist nicht leer
    //nachher:  Diese Anfrage liefert den Inhalt der Wurzel des Binärbaums
    function linkerTeilbaum:Binaerbaum;
    //vorher:    Der Binärbaum ist nicht leer
    //nachher:  Diese Anfrage liefert den linken Teilbaum der Wurzel des Binärbaums
    function rechterTeilbaum:Binaerbaum;
    //vorher:    Der Binärbaum ist nicht leer
    //nachher:  Diese Anfrage liefert den rechten Teilbaum der Wurzel des Binärbaums
    function istLeer:boolean;
    //nachher:  Diese Anfrage liefert den Wahrheitswert "wahr", wenn der Binärbaum leer ist
    function teilbaeumeLeer:boolean;
    //nachher:  Diese Anfrage liefert den Wahrheitswert "wahr", wenn beide
    //          Teilbäume der Wurzel leer sind, die Wurzel also ein Blatt ist
    destructor gibFrei(pMitInhalt:boolean);virtual;
    //nachher:  Der Binärbaum steht nicht mehr zur Verfügung
  end;

implementation

  constructor Binaerbaum.init;
  begin
    kenntInhalt:=nil;
    kenntLinkenNachfolger:=nil;
    kenntRechtenNachfolger:=nil;
  end;

  constructor Binaerbaum.init(pInhalt:TObject);
  begin
    kenntInhalt:=pInhalt;
    kenntLinkenNachfolger:=self.neuerLeererBaum;
    kenntRechtenNachfolger:=self.neuerLeererBaum;
  end;

  constructor Binaerbaum.init(pInhalt:TObject;pLinkerBaum, pRechterBaum:Binaerbaum);
  begin
    kenntInhalt:=pInhalt;
    kenntLinkenNachfolger:=pLinkerBaum;
    kenntRechtenNachfolger:=pRechterBaum;
  end;

  procedure Binaerbaum.ueberschreibeWurzel(pInhalt:TObject);
  begin
    if kenntInhalt=nil then
    begin
      kenntLinkenNachfolger:=self.neuerLeererBaum;
      kenntRechtenNachfolger:=self.neuerLeererBaum;
    end;
    kenntInhalt:=pInhalt;
  end;

  function Binaerbaum.neuerLeererBaum:Binaerbaum;
  begin
    result:=Binaerbaum.init;
  end;

  procedure Binaerbaum.haengeRechtsAn(pBaum:Binaerbaum);
  begin
    if not self.istLeer then
      kenntRechtenNachfolger:=pBaum;
  end;

  procedure Binaerbaum.haengeLinksAn(pBaum:Binaerbaum);
  begin
    if not self.istLeer then
       kenntLinkenNachfolger:=pBaum;
  end;

  function Binaerbaum.WurzelInhalt:TObject;
  begin
    result:=kenntInhalt;
   end;

  function Binaerbaum.linkerTeilbaum:Binaerbaum;
  begin
    result:=kenntLinkenNachfolger;
  end;

  function Binaerbaum.rechterTeilbaum:Binaerbaum;
  begin
    result:=kenntRechtenNachfolger;
  end;

  function Binaerbaum.istLeer:boolean;
  begin
    result:=kenntInhalt=nil;
  end;

  function Binaerbaum.teilbaeumeLeer:boolean;
  begin
    result:=kenntLinkenNachfolger.istLeer and kenntRechtenNachfolger.istLeer;
  end;

  destructor Binaerbaum.gibFrei(pMitInhalt:boolean);
  begin
    if kenntRechtenNachfolger<>nil then kenntRechtenNachfolger.gibFrei(pMitInhalt);
    if kenntLinkenNachfolger<>nil then kenntLinkenNachfolger.gibFrei(pMitInhalt);
    if pMitInhalt and (kenntInhalt<>nil) then
      kenntInhalt.destroy;
  end;

end.




Die Klasse Termbauminhalt:
ausblenden volle Höhe Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
unit mTermbauminhalt;

interface

type Termbauminhalt = class
     zZahl: integer;
     zOperator: string;
     constructor init(pZahl: integer, pOperator: string);
     function istZahl: boolean;
     function Zahl: integer;
     function Operator: string;
     destructor gibFrei;
     end;

implementation

constructor Termbauminhalt.init(pZeichen:char);
begin
     zZeichen := pZeichen;
end;

function Termbauminhalt.zeichen:char;
begin
     result := zZeichen;
end;

destructor Termbauminhalt.gibFrei;
begin
end;

end.


Moderiert von user profile iconMotzi: Code- durch Delphi-Tags ersetzt.
jaenicke
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 19346
Erhaltene Danke: 1754

W11 x64 (Chrome, Edge)
Delphi 12 Pro, C# (VS 2022), JS/HTML, Java (NB), PHP, Lazarus
BeitragVerfasst: Mi 02.06.04 12:13 
Hi!

Also fertigen Code werde ich dir sicher nicht schicken, und wohl auch sonst niemand. Das Forum soll Denkanstöße und Hilfe zu spezifischen Problemen bieten, nicht jedoch Komplettlösungen anbieten.

Ich kann dir mal eine Idee sagen, wie du den Parse-Vorgang durchführen könntest (ich habe mir den Quelltext oben nicht angesehen):

Du müsstest eine Funktion schreiben, die rekursiv aufgerufen wird. Diese Funktion muss den jeweiligen Knoten und die dahineinzusteckende Formel übergeben bekommen. Dann müsste die Funktion den Teil der Formel anaylsieren und ggf in kleinere Teile unterteilen und wieder an die Funktion übergeben. Wenn da jeweils ein neuer Knoten erstellt und mit übergeben wird, in den dann die Funktion die Daten füttert, sollte das funktionieren.

Ein kleines Beispiel (Pseudocode):
Die Knoten werden so gekennzeichnet: 122 heißt 2. Knoten im 2. Knoten des ersten Knotens.

Formel: 2*x+5*y*(z+3)+6

ausblenden Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
Aufruf:
Parse(Topnode, '2*x+5*y*(z+3)+6')

Zerlegung in drei Teile:
Parse(11, '2*x') 
Parse(12, '5*y*(z+3)')
Parse(13, '6') --> fertig

Aus Parse(11, '2*x') wird
Parse(111, '2') --> fertig
Parse(112, 'x') --> fertig

Aus Parse(12, '5*y*(z+3)+6') wird
Parse(121, '5') --> fertig
Parse(122, 'y') --> fertig
Parse(123, 'z+3')

Und schließlich aus Parse(123, 'z+3')
Parse(1231, 'z')
Parse(1232, '3')


Natürlich muss die Aufrufende Funktion stets im aktuellen Oberknoten der übergebenen Unterknoten den Operator speichern. Es darf also nur in einem Term jeweils ein Operator in einem Knoten in Unterknoten zerlegt werden.

ausblenden Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
Hier stehen folgende Operatoren in den Knoten:
1 : '+'
11 : '*'
111 : ''
12 : '*'
121 : ''
122 : ''
123 : '+'


Das musst du dir mal genau ausprobieren, ich denke, dann verstehst du das schon. Zum Parsen musst Du natürlich aus Klammern aufpassen und zuerst nach Summanden und dann nach Faktoren trennen.

Viel Erfolg,
Sebastian