Postfix Notation

Siehe auch https://de.wikipedia.org/wiki/Umgekehrte_polnische_Notation

Ausdrücke wie 2+3*(5-4) sind für uns einfach auszurechnen. Ein Computerprogramm zu schreiben, das solche Ausdrücke korrekt ausrechnet, ist aber nicht trivial. Python (und auch fast alle anderen Programmiersprachen) können solche Ausdrücke selbstverständlich korrekt interpretieren und berechnen. Diese Notation wird Infix-Notation genannt, weil der Operator zwischen den Operanden liegt.

Besonders interessant (und einfach zu programmieren) ist der Umgang mit Ausdrücken in Postfix-Notation, d.h. der Operator folgt auf die Operanden:

• infix: 2+3*(5-4)
• postifx: 2 3 5 4 - * +, d.h. Minus wirkt auf 5 und 4 und 5 4 - wird durch 1 ersetzt. Dann steht noch 2 3 1 * +. Es wird 3 1 * ausgerechnet und durch das Resultat 3 ersetzt. Es bleibt am Schluss noch 2 3 +, also 5.
• (Der Vollständigkeit halber) prefix: add(mul(sub(5,4),3),2) (die Operatoren sind wie Funktionen).

Postfix-Quiz

Ein Stack ist eine Speicherstruktur, die genau zwei Operationen erlaubt:

• Ein Element hinzufügen (push)
• Das zuletz hinuzgefügte Element entfernen (pop)

In Python kann das z.B. mit einem Array (Liste) realisiert werden, wobei die Methoden append und pop verwendet werden können:

a=[]
a.append(7)
a.append(4);
print(a)         #  [7,4]
print(a.pop())   #  4
print(a)         #  [7]
print(a.pop())   #  7
pritn(a)         #  []

Der Stack ist eine grundlegende Stpeicherstrukur, die auch direkt in Prozessoren schon umgesetzt ist. Damit werden z.B. lokale Variablen in Funktionen abgelegt (und je nach Architektur auch auf dem Stack übergeben). Insbesondere die Rücksprungadresse (wo im Code es nachher weiter geht) wird bei Funktionen auf den Stack abgelegt.

Das Auswerten ist extrem einfach und geht den Ausdruck von links nach rechts durch:

• Wird eine Zahl gelesen, wird diese auf den Stack geschrieben
• Wird eine Operation gelesen, werden der Operation entsprechend viele Zahlen vom Stack entfernt, entsprechend verrechnet und das Resultat wieder auf den Stack geschrieben.

Am Ende liegt das Resultat auf dem Stack.

Kriegt man einen Ausdruck als Zeichenkette, muss diese erst in “Tokens”, d.h. einzelne Elemente wie Zahlen und Operatoren zerlegt werden.

• Input: eine String (Zeichenkette mit dem Ausdruck)
• Output: eine Liste mit Strings, die den einzelnen Tokens entsprechen.

Beispiel:

• Input “3 4 5+2 - *”
• Ausgabe [“3”, “4”, “5”, “+”, “-”, “*”]