Umgekehrte polnische Notation

HP 48GX - wissenschaftlicher Taschenrechner mit UPN

Die Umgekehrte Polnische Notation (kurz UPN), auf englisch Reverse Polish Notation (kurz RPN), auch Postfixnotation genannt, ist eine von der Polnischen Notation abgeleitete Notation/Eingabelogik für die Anwendung von Operationen. Bei der umgekehrten polnischen Notation werden zunächst die Operanden eingegeben und danach der darauf anzuwendende Operator.

In der Informatik ist die UPN deshalb von Interesse, weil sie eine stapelbasierte Abarbeitung ermöglicht: Operanden werden beim Lesen einfach auf den Stapel gelegt, ein Operator holt sich die Anzahl an Operanden vom Stapel (Stack), die seiner Stelligkeit entspricht und legt das Ergebnis der Operation wieder auf dem Stapel ab. Am Ende liegt dann das Ergebnis des Terms oben auf dem Stapel. Deshalb bildet die UPN die Grundlage für stapelbasierte Programmiersprachen wie Forth, RPL, PostScript oder die Anweisungsliste im SPS-Bereich.

Beispiele

Es soll 3 und 4 addiert werden. Die Operanden sind dann 3 und 4, der Operator ist "+".

In der Schule ist die erlernte Notation die (sequenziell organisierende) Infix-Notation "3+4". In der umgekehrten polnischen Notation wird hingegen "3 4 +" geschrieben (zwischen 3 und 4 ist ein Leerraum, damit die Zahlen von der Zahl 34 unterschieden werden können).

Weiteres Beispiel (in der Infix-Notation): (3+4)*5. Bei der UPN können die Klammern entfallen, alle Operationen (hier "+" und "*") arbeiten mit den beiden oberen Elementen des Stack. Das Beispiel heißt in UPN dann: 3 4 + 5 * (zuerst wird die Klammer ausgerechnet 3 4+ und dann die entstandene Zahl 7 wiederum mit 5 multipliziert).

Dieses Prinzip ist auch in der deutschen Sprache zu finden:

Wäsche waschen
Brot schneiden
Mehl (und) Eier mischen

Wie häufig auch alltagssprachlich werden erst die Dinge genannt, mit denen man etwas tun kann („Wäsche“), und danach das, was man damit macht („waschen“).

Bei Operatoren mit nur einem Operanden ist UPN auch bei (Taschen-) Rechnern sehr gebräuchlich, die sonst mit der Infix-Notation arbeiten. Beispiele dafür sind die trigonometrischen oder logarithmischen Funktionen, die bei den meisten Taschenrechnern in der Form 25 ln oder 25 sin eingegeben werden (der Operator "ln" bzw. "sin" wird nach dem Operanden "25" eingegeben).

Vorteile/Nachteile

Unter Anwendern wird häufig der Vorteil der UPN zur algebraischen Notation (Infix-Notation) diskutiert.

Die Nachteile:

UPN muss erlernt werden.
Die Gewöhnung an die weit verbreitete Infix-Notation geht verloren.

Die Vorteile:

Implementierung in den Taschenrechnern (z. B. Konstantenautomatik, letzter berechneter Wert = LastX, umfangreiche Vertauschungsoperationen im Stack).
Zwischenergebnisse bei der manuellen Berechnung auf dem Taschenrechner werden angezeigt (bei den neueren Taschenrechnern).
Die Programmierung des Rechners folgt der exakt gleichen Vorgehensweise wie die manuelle Eingabe,
Geringere Anzahl von Tastendrücken, wie das folgende Beispiel zeigt:

Zu rechnen ist: (1+2)*(3+4)

Im algebraischen Modus sind dann die Tasten zu drücken:

(
1
+
2
)
*
(
3
+
4
)
=

Im UPN-Modus (Enter ist eine Taste zum Trennen der Operanden):

1
Enter
2
+
3
Enter
4
+
*

Es sind also drei Tasten weniger zu drücken als im algebraischen Modus (bei aufwendigeren Rechnungen entsprechend mehr). Bei algebraischen Taschenrechnern können gelegentlich eine oder mehrere ")"-Tastendrücke gespart werden, da die "="-Taste auch alle Klammern schließt.

Ein weiterer Vorteil der UPN ist es, dass die Rechnung schrittweise mit sichtbaren Zwischenergebnissen ausgeführt wird. Man kann die Daten also nach und nach weiterbearbeiten. Im algebraischen Modus muss man dagegen vorher wissen was alles noch gemacht werden soll. Dies ist vor allem wichtig, wenn komplexere Berechnungen durchgeführt werden.

Mit der Komplexität der heutigen elektronischen Schaltkreise ist es irrelevant geworden, dass vergleichbare ältere Taschenrechner eine deutlich unterschiedliche Anzahl von Operandenregistern benötigten. Nahezu alle Taschenrechner mit UPN wurden mit nur 4 Operandenregistern hergestellt. Algebraische Taschenrechner dagegen wurden mit bis zu 12 Operandenregistern zu Speicherung von bis zu 11 unvollständigen Operationen hergestellt.

Zur Geschichte

Die Polnische Notation (auch Präfix-Notation oder Łukasiewicz-Notation) verdankt ihren Namen dem polnischen Mathematiker Jan Łukasiewicz, der sie in den 1920er-Jahren entwickelte (eine genauere Datierung ist wohl nicht möglich, vgl. Łukasiewicz 1970 oder Gottschall 2005). Łukasiewicz stellte die polnische Notation als kompakte und klammerfreie Schreibweise für die Aussagenlogik vor.

Łukasiewicz weist selbst darauf hin („On the history of the logic of propositions“, abgedruckt in: Łukasiewicz 1970), dass seine Schreibweise zwar die kompakteste und die erste linear geschriebene klammerfreie Schreibweise ist, aber nicht die erste klammerfreie Schreibweise überhaupt. Das Verdienst, die Logik von der Klammer befreit zu haben, kommt Gottlob Frege mit seiner bereits 1879 veröffentlichten Begriffsschriftnotation zu (siehe auch Begriffsschrift).

Der gleiche Effekt der Klammerfreiheit wird erreicht, wenn der Operator nicht vor den Operanden, sondern danach steht. Diese Variante der polnischen Notation, die als „Umgekehrte Polnische Notation“ bezeichnet wird, wurde vermutlich ebenfalls bereits von Łukasiewicz gesehen. Explizit angesprochen und praktisch verwendet wurde die umgekehrte polnische Notation allerdings wohl erst in den 1950er-Jahren vom australischen Philosophen Charles Hamblin.

Mathematische Grundlage

Mathematisch ist eine Operation nichts anderes als eine Funktion. Eine Funktion $f$ wird allgemein wie folgt geschrieben ( $M$ und $N$ sind beliebige Mengen):

$f:M\to N;x\mapsto f(x)$

Die Sinusfunktion wird dann z. B. geschrieben ( $R$ ist die Menge der reellen Zahlen, hier sind die Mengen $M$ und $N$ gleich):

$\sin :R\to R;x\mapsto \sin(x)$

Die Schreibweise $f(x)$ oder ohne Klammern $fx$ heißt Präfix-Notation oder polnische Notation. Formal kann man anstatt $f(x)$ auch $(x)f$ schreiben (für die Sinusfunktion dann $(x)\sin$ ). Dies ist aber gerade die umgekehrte polnische Notation (Postfix-Notation), man gibt $x$ ein und wendet anschließend die Funktion $\sin$ auf $x$ an.

Da $+$ auch eine Funktion ist, allerdings abhängig von zwei Variablen, kann man $+$ auch schreiben als: $+:R\times R\rightarrow R;(x,y)\mapsto +(x,y)$ . Hier ist $R\times R$ die Paarmenge mit reellen Zahlen. Anstelle von $x+y$ (Infixnotation) wird die Funktionsschreibweise $+(x,y)$ (Präfix-Notation, polnische Notation) benutzt. Nun stellt man das $+$ hinter die Klammern und erhält $(x,y)+$ (Postfix-Notation, umgekehrte polnische Notation), damit auch wieder die polnische Notation, nur für zwei Variablen.

Dieser Sachverhalt kann noch auf $n$ -stellige (wobei $n$ eine natürliche Zahl sei) Funktionen/Operatoren verallgemeinert werden, wobei man dann einen $n$ -stelligen Stack verwendet.

Literatur

Jan Łukasiewicz, L. Borkowski (Hg.): Selected Works, Warschau: PWN 1970
Charles L. Hamblin: Translation to and from Polish notation, The Computer Journal, Volume 5, Issue 3, Oktober 1962, Seite 210–213
Christian Gottschall: Logische Notationen und deren Verarbeitung auf elektronischen Rechenanlagen aus theoretischer, praktischer und historischer Sicht (Diplomarbeit), Wien: 2005

Weblinks

Postfix Notation – mini lecture (engl.)
Eine Einführung in die umgekehrte polnische Notation bei HP (de)
http://www.hpmuseum.org/rpn.htm Verwendung von RPN bei HP (engl.)
Einführung in UPN von ActiveVB mit Implementierung
RPN Interface für den TI-89 und TI-92+ Stellt dem TI-89 und TI-92+ RPN/UPN zur Verfügung. (Der Funktionsumfang des Computer Algebra System ist im RPN/UPN Modus nicht eingeschränkt)(engl.)
http://www.hpcalc.org/ – Emulatoren und Software für HP Taschenrechner (engl.)
http://www.clk-calculator.de/ – RPN/UPN Taschenrechner für den PC
http://www.h-bauer.de/index.html?rpncalc,ger – Kompakter RPN/UPN-Rechner für den PC (Freeware)