Erstellung eines Baums aus Postfix-Notation

[MiBo]

Hi,

ich habe folgende Aufgabenstellung, Lösung ist bekannt, aber ich komme nach stundenlangem herumprobieren und analysieren nicht auf den Lösungsweg. Stehe wahrscheinlich extrem auf dem Schlauch, aber könnte mir das bitte jemand Schritt für Schritt erklären?

Betrachten Sie folgenden arithmetischen Ausdruck in Postfix-Notation, d.h. der Operator steht immer hinter den Operanden (umgekehrte polnische Notation):

a b + c * d e f - / - g * h +

a) Erzeugen Sie daraus einen Baum, dessen Post-order-Traversierung diesem Ausdruck entspricht.

Geben Sie den Ausdruck in "normaler" Notation an.

Wäre super, wenn mir jemand helfen könnte, schreibe nächste Woche Prüfung und das wäre dann ein Lückenthema :floet:

Danke im vorraus und viele Grüße

MiBo

P.S.: Ich hätte vielleicht dazusagen sollen, dass ich keinen Quelltext oder sowas suche, sondern einfach nur die Umsetzung mit Papier, Hirn und Bleistift

[Muadibb]

also, ich habe mal gerade Wikipedia benutzt, um zu sehen, wie das geht

Der erste Teil scheint recht klar aus meiner Sicht:

ab+c* wird zu (a+*c, wie es auch in der Beschreibung bei Wikipedia als Beispiel gegeben ist.

Nun folgt meiner Meinng nach eine Verkettung:

(a+*c-(d/e-f)

g* kann sich jetzt nur auf die 2 Klammer beziehen oder auch auf die Verkettung als Ganzes, also:

((a+*c-(d/e-f))*g oder (a+*c-(d/e-f)*g. Ich tendiere zum 2. Weg.

Zuletzt noch das h+ anhängen:

(a+*c-(d/e-f)*g+h

Da Du ja die Lösung kennst, kannst Du ja mal posten, ob ich nah dran bin

Anhand der Lösung könnte ich Dir das eventuell auch besser erklären und versuchen Regeln abzuleiten

[Schachcomputerfreak]

OK, ich gehe mal davon aus, dass Du mit Aufgabenteil A nicht zurechtkommst (wenn Du mit B nicht klar kommst, hast Du wirklich ein Problem...)

Wie sollst Du den Baum erzeugen? Nur zeichnerisch? Oder in Form von Programmcode?

Die grundsätzliche Vorgehensweise ist folgende:

Wenn noch Eingabetoken vorhanden sind

Erzeuge einen Knoten aus dem nächsten Eingabetoken und lösche es

sonst

Löse einen Fehler aus

Wenn der Knoten einen Operator enthält:

Parse einen Baum aus der Eingabe und hänge ihn links ein Parse einen Baum aus der Eingabe und hänge ihn rechts ein

Gib den Knoten zurück

Eine sehr genaue Erklärung mit Programmcode erhälst Du auf folgender Seite.

http://www.cl.uni-heidelberg.de/kurs/ws04/prog1/html/page048.html

und wenn Du nach "Postorder Traversierung" mal googlest, dürftest Du noch einiges mehr finden.

[MiBo]

Hm, danke erstmal für die Antworten bis jetzt.

Also mit Aufgabenteil b habe ich nicht so die Probleme, eher mit a. Mir ist nicht ganz klar, nach welchen Regeln man das ganze dann in einen Baum umsetzt (wo fängt man an, wie geht es weiter, etc. ...). Muss einfach nur nen Baum zeichnen, kein Quellcode, kein Pseudocode, nichts.

Post-order und alle anderen -order machen mir überhaupt keine Probleme, also quasi Baum in Liste überführen.

Hab da wohl eine Blockade, die das andersrum net kann ^^. Also falls jemand noch nen Tip hat, bitte her damit

Viele Grüße

MiBo

[Bubble]

Postfix: Operator steht hinten, die beiden Operanden davor. Ist der eine Operand selbst ein Operator, muss sein Wert mit Hilfe der vor ihm stehenden Operanden gebildet werden. Nimm also Deine Eingabe und verarbeite sie von rechts nach links (von hinten nach vorne). Also besteht die Wurzel des Baumes aus einem "+", ein Blatt/Knoten ist ein "h", das 2. Blatt/Knoten ist der Operator "*". Dieser hat wieder die Unterknoten "g" und "-". So hangelst Du Dich komplett durch, bis Du den Baum aufgebaut hast.

[MiBo]

Das hilft schonmal enorm weiter, jetzt komme ich bis zur Hälfte :beagolisc

Dankeschön ... mal sehen, ob ich das noch weiter schaffe *g*.

Grüße

MiBo