Auswertung von Postfix-Ausdrücken

FJ15.A2_2

2. Geben Sie an, wie man den Ausdruck in Postfix-Notation unter Nutzung eines geeigneten Datentyps auswerten kann:

Auswertung von Postfix-Ausdrücken

 

Terme in Postfix-Notation lassen sich besonders bequem mit Hilfe eines Kellers errechnen.

Dazu wird der Term von vorne nach hinten durchlaufen. Zahlen werden in den Keller gespeichert. Wenn man auf ein Rechenzeichen stößt, werden die letzten beiden Zahlen aus dem Keller genommen und (wie gewohnt) mit diesem Rechenzeichen verknüpft. Dabei kommt die erste Zahl, die aus dem Keller genommen wird, hinter das Rechenzeichen, die andere Zahl vor das Rechenzeichen. (Dies entspricht der Reihenfolge, in der die Zahlen im Term vorkamen. Denn 5 2 – entspricht 5-2 und nicht 2-5.) Das Ergebnis der Rechnung wird anschließend wieder in den Keller gesteckt. Am Ende steht im Keller der Wert des Terms.

 

Aufgabe:

Berechnen Sie die Werte der folgenden Postfix-Terme mit Hilfe eines Kellers. Zeichnen Sie auch den Keller und streichen Sie dort (beim Herausnehmen) die Werte so durch, dass sie lesbar bleiben.

a)      3 5 10 * - 2 5 / - 9 2 *  +

b)      10  2 / 5 + 3 – 10 5 - + 2 3 + -

c)      5 1 2 + * 2 / 2 + 5 9 * -

d)      7 3 + 2 4 + 9 * - 6 3 / - 7 2 5 + * 2 / +

Postfix-Ausdrücke haben gegenüber Termen in Infix-Schreibweise zwei Vorteile:

1.) Es werden keine Klammern und keine Vorrangregeln benötigt, da durch den Postfix-Ausdruck der zugehörige Termbaum und damit die Reihenfolge der Berechnungen eindeutig festgelegt.

2.) Man kann die Werte der Terme mit Hilfe eines Kellers sehr einfach berechnen.

Deshalb eignet sich die besonders gut, um eine einfachen Taschenrechner zu programmieren.

 

Die Infix-Schreibweise hat dagegen den Vorteil, dass die Rechenzeichen die Zahlen voneinander trennen Dadurch werden Fehler durch zu kleine Lücken zwischen den Zahlen vermieden.(Zum Beispiel sieht man auch bei flüchtiger Schreibweise sofort, ob 10 oder 1 und 0 gemeint ist.)