Entwickler-Ecke
Delphi Language (Object-Pascal) / CLX - aus infix aufgabe Binärbaum erstellen
praesident118 - Sa 12.04.08 13:32
Titel: aus infix aufgabe Binärbaum erstellen
Hallo miteinander,
wir müssen in der Schule folgendes Programm schreiben:
Der user soll einen vollständig geklammerten Infix-Term eingeben. z.b. ((3+5)*9)+(3*7)
Aus diesem soll dann mittels canvas ein Binärbaum gezeichnet werden.
Das ganze soll rekusiv erfolgen, allerdings habe ich im Moment noch nicht mal einen Ansatz.
Hättet ihr viellt. ein paar Lösungsvorschläge oder ein Beispielprogramm (z.B. Welche Parameter sollte ich verwenden?) ?
Ich muss aber noch dazu sagen, dass wir noch keine Klassen behandelt haben.
Wäre euch für eure Hilfe sehr Dankbar
mfg
Martok - Sa 12.04.08 18:29
Hm, diese Aufgabe würde ich in mehre Teile zerlegen... eigentlich in 2 :roll:
1. String parsen
2. Ausgeben
Erstmal brauchst du ein Datenformat, dass den Baum hält. Irgendwas wie
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
| PLeaf = ^TLeaf;
TLeaf = record
Operation: (ltValue, ltAdd,ltSubtract,ltDivide,ltMultiply);
Op1,Op2: PLeaf;
Value: integer;
end; |
So, da müssen deine Daten rein. Die Struktur dürfte klar sein: es wird gespeichert, welche Art dieser Knoten ist. Wenn er eine Rechenoperation ist, dann sind die Operatoren wieder als Leaf-Objekte in Op1 und Op2 gespeichert. Ist der Knoten ein Wert (Operation = ltVlaue), dann steht selbiger in Value.
Du musst also rekursiv immer an Operatoren trennen und mit 'links' und 'rechts' genauso verfahren, bis nur noch einfache Werte drin stehen. Diese kommen dann in Value-Knoten.
Darstellen kann man das dann auch relativ einfach, einfach vom Root nach unten durchgehen und ausgeben. Auch wenn ich kein Canvas, sondern ein TTreeView verwenden würde, aber warum einfach, wenn's auch kompliziert geht...
Hoffe mal das dir das als Denkanstoß hilft. Irgendwann wollte ich das auch mal machen, hatte damals aber die Idee so nicht. Ich glaube ich schreibe auch mal ein kleines Beispielprogramm...
Hidden - Sa 12.04.08 19:36
 Martok hat folgendes geschrieben: |
Delphi-Quelltext 1:
2:
3:
4:
5:
6:
| PLeaf = ^TLeaf;
TLeaf = record
Operation: (ltValue, ltAdd,ltSubtract,ltDivide,ltMultiply);
Op1,Op2: PLeaf;
Value: integer;
end; | |
Hi,
Sie haben sich noch nicht mit Klassen beschäftigt, ob sie dann Pointer schon kennen :?:
Zur Erklärung: Ein Pointer wird durch ein Dach(
^) gekennzeichnet und enthält eine Speicheradresse, über die auf den entsprechenden Speicher zugegriffen werden kann. Pointer(zu Deutsch: Zeiger) werden von Delphi oft
implizit verwendet, d.h., wenn du eine Variable als TLeaf deklarierst, mach Delphi oft Pointer daraus.
Zum Umgang mit Pointern: Der Operator(Operatoren sind z.B. +, - oder *) "@" liefert die Speicheradresse der nachstehenden Variable. Bei der Deklaration von Pointern kommt das Dach danach(MyPointer^). Verwendest du den Pointer nun, so wird zunächst einmal auf die Speicheradresse zugegriffen, z.B.
MyPouinter := @MyObject. Willst du nun auf den Speicher, statt auf die Speicheradresse, zugreifen, so liefert ein Dach nach dem Pointer(
MyPointer^) den Speicher, auf den die Adresse/der Pointer zeigt.
Was Martok also vorschlägt ist, dass z.B.
(3 + 4) * (6 + 2) als eine Operation angesehen wird, die aus den Operationen
3 + 4 und 6 + 2 besteht. Das Ausrechnen eines Terms würde dann über eine Methode verlaufen, die einen TLeaf-Record als Parameter verwendet und, wenn er wiederum aus zwei Operationen besteht, sich selbst(rekursiv also) wieder aufruft, um das Ergebnis seiner Einseloperationen zu erhalten.
Wenn ihr noch keine Pointer behandelt habt, lass die deklaration als Pointer einfach weg:
Delphi-Quelltext
1:
2:
3:
4:
5:
| TLeaf = record
Operation: (ltValue, ltAdd,ltSubtract,ltDivide,ltMultiply);
Op1,Op2: TLeaf;
Value: integer;
end; |
Delphi behandelt diese Variable dann implizit als Pointer.
Habt ihr euch schon mit
nil beschäftigt? Das ist ein Pointer auf eine leere Speicheradresse, also ins nichts.
mfG,
Martok - Sa 12.04.08 20:14
Naja, die Aufgabe sah mir nach einem Paradebeispiel für Binary Trees aus, und die werden meistens verpointert^^
Lassen wir den praesidenten mal was dazu sagen ;)
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!