Hilfe bei der Implementierung eines Baums / Abspeicherung eines Ausdrucks

[JonesSch]

Hallo zusammen,

Problembeschreibung:
Bei der Aufgabe geht es darum einen beliebigen Ausdruck (in Präfixnotation) in einen Baum abzuspeichern. z.B. ~ 4 6 + 3 -7 1, wobei die Knoten eine einfache verkette Liste darstellen sollen. Ich habe bereits versucht das mit Stift und Papier nachzuvollziehen (siehe Anhang).
Es handelt sich dabei um einen Baum der keine Einschränkungen an der Anzahl der Kindknoten hat:

[CODE lang="java" title="Baum ohne Einschränkungen"]class TreeObjekt<T> {
private TreeObjekt<T> parent = 0;
private TreeObjekt<T> leftChild = 0;
private TreeObjekt<T> rightSiblings = 0;
private T data;
...
}[/CODE]

Dabei ist das Attribut leftChild die head-Referenz und das Attribut rightSibling entspricht der next Referenz einer einfach verkettete Liste (siehe Abbildung rot umkreist).

Ergebnis (Wie soll es am Ende aussehen):
GUI mit Eingabefeld eines Ausdrucks in Präfixnotation (eine Zeichenkette mit Leerzeichen als Trenner), ein Button zum Starten der Berechnung, Ausgabe des Baumes in einem Panel oder ähnliches.

Ich habe das, wie auf der Zeichnung zu sehen, versucht herunter zu brechen auf kleine Teilschritte und zu verdeutlichen wie das Programm am Ende aussehen soll. Nur sobald ich mich an Java setze bin ich überfordert und komme nicht voran / weiß nicht wie ich die Theorie in die Praxis umsetze. Kann mir da jemand eine Hilfestellung geben, wie man da am Besten vorgeht ggf. noch weiter herunterbricht, sodass einem die Java Implementierung nicht als Unmöglich vorkommt?😅

Danke im Voraus
LG

 

[kneitzel]

Dann formuliere doch erst einmal genau den Algorithmus wie er funktioniert. Also in Worten exakt beschreiben, was getan werden soll.

So eine Skizze ist hilfreich um einen Überblick zu bekommen aber es ändert nihts daran, dass der Algorithmus im Detail beschrieben werden muss.

Edit: Aus deinber Skizze werde ich auch nicht wirklich schlau. Was für ein Ausdruck hast Du denn da wie zu so einem Baum umgebaut?

 

[JonesSch]

Danke für deine Nachricht. Ich hoffe das gibt einen besseren Überblick.

Was für ein Ausdruck hast Du denn da wie zu so einem Baum umgebaut?

Definition der Ausdrücke:
Es seien a ,b , c ,d ,e reelle Zahlen und ~ ,& ,? drei (erfundene) Operatoren, die wie folgt definiert sind:

• Der Ausdruck ~ a b c in Präfixnotation ist gleichbedeutend mit a+b−c in der üblichen Schreibweise, also z.B. ~ 2 3 4 = 1 .
• Der Ausdruck & a b c d e in Präfixnotation ist gleichbedeutend mit dem Ausdruck a+b+c – d – e in der üblichen Schreibweise, also z.B. & 1 2 3 4 5 = −3 .
• Der Ausdruck ? a b c d in Präfixnotation ist gleichbedeutend mit dem Ausdruck a+b – c+d in der üblichen Schreibweise, also z.B. ? 2 3 4 5 = 6

Ein Ausdruck mit mehreren Operatoren sieht dann z.B. so aus ~ 4 6 ~ −7 3 1. Gerechnet wird 4+6−(−7+3−1) = 15 .

Ablauf des Algorithmus:
1. Es soll über eine GUI ein Ausdruck in Präfixnotation (also eine Zeichenkette mit Leerzeichen als "Trenner", also Komponenten des Ausdrucks nicht einzeln eingeben) eingegeben werden. z.B. ~ 4 6 ~ −7 3 1
2. Ein Button zum starten der Berechnung.
3. Nach dem Klicken auf diesen Button, soll der eingegebene Ausdruck (~ 4 6 ~ −7 3 1) in dem Baum abgespeichert werden (siehe Skizze vorherige Nachricht)

• Es wird ein neuer Baum erstellt
• Der Baum ist leer -> Es wird ein neuer Knoten erstellt und der erste Wert (~) hineingeschrieben.
• Danach wird der zweite Ausdruck genommen (4) und auf der zweiten Ebene abgespeichert. Das gleiche passiert mit dem 3ten (6) und 4ten (~) Ausdruck.
• Bei dem 4ten Ausdruck (dem ganz rechten Element) fächert sich der Baum weiter auf, auf die nächste Ebene werden die anderen Ausdrücke (7,3, 1) nebeneinander beschrieben, sodass es so aussieht wie auf der Skizze.
• Zur Auswertung/Berechnung des Ausdrucks soll eine rekursive Methode geschrieben werden.
• Der Baum soll in einem Panel ausgegeben werden. Die Ausgabe sieht dann wie folgt aus:
  • ~ (1. Baumebene)
  • 4, 6, ~ (2. Baumebene)
  • -7, 3, 1 (3. Baumebene)

 

[kneitzel]

Also was mich hier jetzt schon stört ist der Ausdruck: "~ 4 6 ~ −7 3 1" -> der dürfte nach meinem Verständnis schlicht ungültig sein!
(Wobei die Frage ist, was ~ für ein Operator sein soll. Wenn es der ~ Operator aus Java sein sollte, dann wäre die Aufagabe etwas komplexer, aber egal ... dazu kommen wir später ...)

Und Du beschreibst zwar, was der Algorithmus macht (im groben) aber du gibst keine klare Handlungsanweisung.

Betrachten wir einmal die Operatoren ganz allgemein: Ein Operator hat eine feste Anzahl an Operanden. Es gibt also den Operator + und der bekommt zwei Operanden. Darstellen lässt es sich dann in unterschiedlichen Notationen:
Infix: a + b
Präfix: + a b
Postfix: a b +
a und b können dabei beliebige, weitere Ausdrücke in der jeweiligen Notation sein.

Daher gibt es nun eine Menge an Operatoren, die man unterstützt. Üblich sind z.B. * / + -, aber es kann beliebige Operatoren geben. Die Berechnung der Quadratwurzel könnte z.B. auch definiert sein als SQRT. Diese hätte aber nur einen Parameter. Ein Ausdruck wäre also in Präfix: SQRT a

Und von mir aus auch ~, was in Java die bitweise Negierung aller Bits wäre. Hätte dann auch nur ein Operand.

Daher wäre der Ausdruck von Dir da oben nach "~ 4" fertig. Da es aber weiter geht, ist es ungültig. Wäre ~ ein Operand mit zwei Operanden, dann wäre der Ausdruck nach "~ 4 6" beendet. Aber der Ausdruck geht ja noch weiter - also muss es 3 Operanden geben? Dann hätten wir:
~ a b c mit
a= 4
b= 6
c= ~ - 7 3 1
Bei C müsste man dann wieder aufteilen und 3 Operanden haben. Die haben wir aber nicht. - 7 3 wäre ein Operand und damit hätte man nur 2 Operanden. Das ist so also schlicht nicht gültig. (Kann man sich vor Augen führen, denn es ist sonst einfach nicht zwingend eindeutig, wohin welches Operand gehört.
Beispiel: op1 op2 a b c d e f g
Wenn man da Klammern einsetzt, dann ist klar: die öffnende Klammer wäre zwischen op1 und op2, aber die schließende Klammer kann fast beliebig danach kommen. (so op1 und op2 0...n Parameter bekommen könnten)

 

[temi]

Wobei die Frage ist, was ~ für ein Operator sein soll.

Die Operatoren sind allerdings oben definiert worden

 

[kneitzel]

Die Operatoren sind allerdings oben definiert worden

Oh, super! Das habe ich irgendwie komplett überlesen! Vielen Dank! Damit ergeben die Posts deutlich mehr Sinn und die Fehler, die vermutet habe, sind alle hinfällig. @JonesSch: Sorry für meine Fehler / Oberflächigkeit und @temi: Recht herzlichen Dank für diesen wichtigen Hinweis!

Und dann wird auch schnell klar, wo mein Fehler lag - warum der Ausdruck in meinen Augen falsch schien:
"~ 4 6 ~ −7 3 1"
-7 => Das ist eine negative Zahl. Operatoren sind mit Leerzeichen getrennt. Und damit ist der Ausdruck dann natürlich gültig. da es eben kein - 7 3 (also 7 - 3) war!

Der Baum, der gezeichnet wurde, ist dann prinzipiell auch gültig - nur die Pfeile sind dann noch etwas, das ich ggf. anders darstellen würde.

Versuchen wir noch einmal einen neuen Anfang - hoffentlich kann ich Dir jetzt besser helfen @JonesSch:

Wenn Du einen Ausdruck hast wie "~ 4 6 ~ −7 3 1" - wie würdest Du den Baum zeichnen? Evtl. findest Du einen Weg, wie Du Zeichen für Zeichen oder Token für Token vorgehen könntest. Also etwas wie:

Ich nehme mir das erste/nächste Element / Token und dann schaue ich:
- ist es ... dann ...

Wenn Du so alle Möglichkeiten beziffern kannst, dann wirst Du ggf. einen relatriv einfachen Algorithmus finden. Dazu als Hinweis einfach einmal folgendes Betrachten:
"5" ist ein gültiger Ausdruck. Was machst Du bei so einem Ausdruck?
"~ A B C" ist ein gültiger Ausdruck... nur was kann dann dieses A, B und C sein?
(Bei einem Baum hat man oft typische Elemente wie: Blätter (Elemente ohne Child-Elemente) und neuen Bäumen (Also Elemente, die eine Wurzel haben und Child Elemente)

Hilf das evt. etwas, um etwas zu formulieren, wie ich es etwas skizziert habe mit:
Ich nehme mir das erste/nächste Element / Token und dann schaue ich:
- ist es ... dann ...
- ist es ... dann ...
- ist es ... dann ...

 

[JonesSch]

Erstmal danke für die Antworten! Ich versuche es mal nach deiner Beschreibung zu formulieren 😅

Wenn Du einen Ausdruck hast wie "~ 4 6 ~ −7 3 1" - wie würdest Du den Baum zeichnen? Evtl. findest Du einen Weg, wie Du Zeichen für Zeichen oder Token für Token vorgehen könntest. Also etwas wie:

Ich glaube ich würde den Baum als verkette Liste implementieren, da jedes Element mit einander verknüpft ist (Wie an den Pfeilen in der Skizze zu erkennen). Also das ich den Ersten Ausdruck nehme (~) mit einer Referenz zum nächsten Element (4) usw.

Ich nehme das erste Element und schaue, ob der Baum leer ist
- Ja -> neuen Baum erstellen und Element einfügen (das ist dann mein root)
- Nein -> neuen Knoten erstellen

Zweites Element und vergleichen, ob der Baum leer ist
- Nein -> neuen Knoten erstellen
- Diesem Element eine Referenz auf das erste Element zuweisen und als "leftChild" deklarieren

Drittes Element das gleiche

Vierte Element das gleiche

Fünfte Element das gleiche + als "rightSibling" definieren

Sechste Element das gleiche + eine head-Referenz auf seinen Parent (rightSibling)

usw. bis ich den gesamten Ausdruck eingelesen habe.
---------------------------------------------------------------------------------------------------------------------------------------------------------------
Doch da stoße ich schnell auf Probleme und zwar stellt sich mir die Frage wie ich daraus eine Baumstruktur erhalte?

Bei einer Liste habe ich ja ein head- Referenz die den Anfang der Liste kennzeichnet und eine next-Referenz, die die Referenz auf das nächste Element in der Liste kennzeichnet. Nur laut der Aufgabenstellung soll das Attribut "leftChild" (also in dem Fall die 4) eine head-Referenz auf eine einfach verkettete Liste sein und das Attribut "rightSibling" (also in dem Fall der 4te Ausdruck (~) ) die next-Referenz einer einfach verketteten Liste sein.
Ich habe Schwierigkeiten in der Vorstellung, wie ich die beiden Datenstrukturen miteinander verbinde und das in Java umsetzen kann...

 

[kneitzel]

Ich denke, dir fehlr noch ein wichtiger Ansatz:

Erst einmal hast Du in der Skizze doch einen Baum gemacht (Wenn man mal die Pfeile vergisst):
- Was steht in den Knoten des Baumes?
- Was steht in den Blättern des Baumes?

Ich denke, dies ist der erste wichtige Punkt ist, den du erkennen müsstest. Dazu einfach einmal alle Knoten deines Baumes auflisten und dann alle Blätter.

 

[JonesSch]

Dann würde die Struktur so aussehen oder?

~ -> Wurzel / root
4 -> Blatt (Knoten ohne Blätter)
6 -> Blatt
+ -> Knoten
3 -> Blatt
-7 -> Blatt
1 -> Blatt

 

[kneitzel]

Ok, kannst du das denn allgemein ausdrücken?
Was ist in allen Knoten?
Was ist in allen Blättern?

 

[kneitzel]

Ich will einmal einen Schritt weiter gehen um besser aufzuzeigen, worauf ich hinaus will und wie man das nutzen kann um zu einem Algorithmus zu kommen.

Das erste, was man sehen sollte, ist, dass Zahlen immer zu einem Blatt werden.
Operatoren werden zu einem Knoten, d.h. sie haben die Operator und brauchen dann die notwendigen Parameter.
Wenn man sich also den ~ Operator anschaut, dann braucht dieser 3 Parameter.

Das wäre, worauf ich hinaus wollte. Man kann es auch ohne diesen Baum und die Aufteilung in Blätter und Knoten überlegen, in dem man schaut, was ein Ausdruck sein kann:
a) Eine Zahl. "5" ist ein gültiger Ausdruck. Der Ausdruck Zahl hat einfach einen Wert. Also bei dem Beispiel wäre dies 5.
b) Die Operation ~ - diese hat 3 weitere Ausdrücke: a b und c. Also muss der Ausdruck Tilde drei Ausdrücke speichern.

Das wäre jetzt alles, was man braucht um das darzustellen:
Ausdruck ist dann z.B. ein Interface. Braucht jetzt erst einmal noch nichts. evaluate() könnte man sich da überlegen, aber diesbezüglich habe ich die Aufgabe jetzt nicht überprüft.

- Zahl implementiert Ausdruck, enthält einen Wert
- Tilde implementiert Ausdruck, enthält 3 Ausdruck: a, b und c.

Das Parsen des Ausdrucks kann man dann so ausführen:
a) Umwandlung des Strings in eine Queue. Aus "~ 4 6 ~ −7 3 1" wird dann eine Queue gemacht, die die einzelnen Teile enthält: "~", "4", "6", "~", "-7", "3" und "1"
b) Dann wird die Queue ausgewertet. Das bedeutet ich habe eine Methode, die eine Queue entgegen nimmt und mit einen Ausdruck zurück gibt (Ausdruck ist ein Interface, das ich bereits erwähnt habe).

Beispiel: "5" ist das einzige Element: dann wird eine Instanz von Zahl zurück gegeben. Diese Instanz von Tilde wird den Ausdruck einfach parsen und den Wert speichern.
Beispiel "~", "1", "2", "3" wird übergeben: Es muss eine Instanz von Tilde zurück gegeben werden. Die Instanz braucht nun a, b, und c.
Also die "~" haben wir schon ausgewertet und entnommen. Also bleibt "1", "2", "3". Hier müssen wir nun nur erzeugten Tilde Instanz zuweisen: a ist der nächste Ausdruck. Ebenso das b und zuletzt für c.

Das kannst Du dann als nächstes für verschachtelte Ausdrücke durchspielen: Funktioniert das z.B. auch für "~", "~", 1, 2, 3, 4, 5?

Und dann musst Du dir noch die übrigen Operatoren überlegen, die Du genannt hast. Wie sind diese aufgebaut?

 

[JonesSch]

Vielen Dank nochmal für die Beschreibung, so wird es auf jeden Fall verständlicher!

Ich habe durch deine Beschreibung mir nochmal eine neue Struktur / Konzept überlegt, wie ich es umsetzen könnte:

1. Klasse TreeObjekt, wo ein Objekt von Typ Baum erstellt wird und die Methode createTree mit der ich den Baum zeichnen möchte.

Das habe ich mir so gedacht (wie Du bereits sagtest in einer Queue)​

​

Ein Element (Treeobjekt) erstellen und den Baum zeichnen / ausgeben -> am Anfang Überprüfen, ob die Queue leer ist:​

• [CODE lang="java" title="Einfügen eines neuen Elementes"]class TreeObjekt<T>{
  private TreeObjekt<T> parent = 0; // Referenz auf das vorherige Element (Elternknoten)
  private TreeObjekt<T> leftChild = 0; // head
  private TreeObjekt<T> rightSiblings = 0; // tail
  private T data; // Wert des Elementes
  
  // neues Element in die Queue einfügen
  public void createTree( T n ){
  MyTreeObject obj = new MyTreeObject (null, null, n );
  // Baum leer?
  if (leftChild == null) {
  leftChild = obj; // obj = neues Element
  obj.parent = leftChild
  rightSiblings = obj;
  } else { // nicht leer
  leftChild.rightSiblings = obj;
  obj.parent = head;
  }
  }
  [/CODE]

b) Dann wird die Queue ausgewertet. Das bedeutet ich habe eine Methode, die eine Queue entgegen nimmt und mit einen Ausdruck zurück gibt

2. Zur Auswertung/Berechnung des Ausdrucks eine rekursive Methode. Wie kann ich dieser Methode die gesamte Queue mit den gespeicherten Werten übergeben?

public double eval(...)​

Das Parsen des Ausdrucks kann man dann so ausführen:
a) Umwandlung des Strings in eine Queue. Aus "~ 4 6 ~ −7 3 1" wird dann eine Queue gemacht, die die einzelnen Teile enthält: "~", "4", "6", "~", "-7", "3" und "1"

Kannst du mir das vielleicht nochmal erklären, wie ich das konkret umsetzen kann?
Also wenn ich jetzt die Eingabe ~ 4 6 ~ -7 3 1 genau so eintippe, dass ich daraus eine Queue mit String werten bekomme, wie du es oben beschrieben hast?

Mein Ansatz zur Auswertung wäre jetzt, dass ich die toString-Methode verwende, dort die 3 Fälle der 3 Operatoren (~ ? &) in einem Switch Case unterbringe, also 3 regeln erstellen die z.B. so aussehen:

wenn ~ dann ist es gleich a + b -c
wenn ? dann ist es gleich a+b – c+d
wenn & dann ist es gleich a+b+c – d – e
Dann iteriere ich durch die gesamte Queue und berechne die einzelnen Strings hintereinander.

So stelle ich mir das zumindest in der Theorie vor. Ich hoffe ich bin da nicht komplett auf dem falschen Weg? 😅

 

[kneitzel]

Also das mit der Queue (Schlange oder Warteschlange) war ein Begriff, der die erwartete Funktionalität (FIFO: First In, First Out) wieder gegeben hat. Bei der Aufgabe scheint es aber eine klare Vorgabe zu geben:

wobei die Knoten eine einfache verkette Liste darstellen sollen.

Vermutlich werdet Ihr eine solche Liste haben - vermutlich aus früheren Unterrichtseinheiten.

Und das kann dann bedeuten, dass Du da den String nicht erst umsetzen musst - statt dessen kannst Du direkt eine solche einfach verkettete Liste erzeugen. (So wäre ggf. mein Verständnis der Aussage).

Ansonsten Wäre dies einfach umwandelbar - String.split kann genutzt werden, um z.B. an Leerzeilen den String aufzusplitten. Die Elemente des Arrays packst Du dann nur noch in die Liste. Und dann kannst Du bei der Liste nacheinander immer das erste Element entnehmen und auswerten.

Mein Ansatz zur Auswertung wäre jetzt, dass ich die toString-Methode verwende

Das verstehe ich jetzt nicht. Du hast ja schon einen String und darauf kannst Du schon ein switch aufbauen. Du musst aber auch an den Fall denken, dass es eine Zahl sein kann ....

Und deine Aussagen von wegen "dann ist gleich ...." verstehe ich so auch nicht. Du sollst einen Baum aufbauen:

Bei der Aufgabe geht es darum einen beliebigen Ausdruck (in Präfixnotation) in einen Baum abzuspeichern.

Daher darauf fokussieren, was raus kommen soll. Und das ist keine Rechnung. Was mit dem a, b und c (bei dem ~) dann berechnet werden müsste, ist für den Baum egal. Da ist nur wichtig: Beim Knoten ~ gibt es 3 Zweige. Was musst Du also machen? (Eigentlich hatte ich das ja zuvor auch schon detailiert beschrieben.