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 Schreibweise bzw. Eingabelogik für die Anwendung von Operationen. Bei der umgekehrten polnischen Notation werden zunächst die Operanden niedergeschrieben bzw. 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 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.

Taschenrechner mit der Umgekehrten Polnischen Notation besitzen eine meist auffällige Enter-Taste, dafür fehlen die Klammertasten und die Gleichheitstaste. Eine konventionelle Löschtaste zur Einleitung der Berechnung fehlt ebenfalls, da nicht mehr benötigte Ergebnisse während der Berechnungen automatisch aus dem Stapel geschoben werden. Eine modifizierte Löschtaste wird allerdings zur Beseitigung von Tippfehlern verwendet.

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 Stapels. Das Beispiel heißt in UPN dann: „3 4 + 5 ×“ (zuerst wird der Klammerausdruck „3 4 +“ausgerechnet, danach die hierbei entstandene Zahl 7 mit 5 multipliziert).

Dieses Prinzip ist auch in der deutschen Sprache zu finden:

• Die Wäsche waschen.
• Das 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“).

Sprachlich kann man die Unterschiede der Infix-Notation „(3+4)×5“ und der UPN „3 4 + 5 ד wie folgt veranschaulichen:

• Statt „3 plus 4, mal 5“ sagt man „3 und 4 addieren und mit 5 multiplizieren“.

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 2 5 ln oder 2 5 sin eingegeben werden (der Operator „ln“ bzw. „sin“ wird nach dem Operanden „25“ eingegeben).

Vor- und Nachteile

Der UPN-finanzmathematische Taschenrechner HP-12C wird seit 1981 bis heute gebaut

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

Der augenfälligste Vorteil der UPN ist, dass sie im Allgemeinen mit einer geringeren Anzahl von Tastendrücken auskommt. Um zum Beispiel die Rechnung (1+2)×(3+4) vorzunehmen, muss man im algebraischen Modus zwölf Tasten betätigen:

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

Im UPN-Modus sind nur neun Tastendrücke erforderlich:

1 Enter 2 + 3 Enter 4 + ×

Es sind also drei Tasten weniger zu drücken als im algebraischen Modus; bei aufwändigeren Rechnungen ist die Ersparnis entsprechend größer.

Ein weiterer Vorteil der UPN ist es, dass die Rechnung stets schrittweise und mit sichtbaren Zwischenergebnissen ausgeführt wird; man kann die Daten also nach und nach weiterbearbeiten; allerdings zeigen auch viele algebraische Taschenrechner Zwischenergebnisse, so weit das möglich ist, zum Beispiel beim Betätigen der )-Taste den Wert des aktuellen Klammerausdrucks.

Die Verfügbarkeit von Zwischenergebnissen erleichtert es nicht nur, die Eingaben zu kontrollieren und Fehler zu identifizieren, sondern erlaubt es im Zusammenhang mit den bei UPN verfügbaren Vertauschungsoperationen innerhalb des Stapels, jedes Zwischenergebnis einfach zu speichern – etwa in Speicherregistern – und später weiterzuverarbeiten.

Die Programmierung eines UPN-Rechners folgt normalerweise exakt der manuellen Eingabe einer Berechnung, was vor allem bei häufigen kurzen Rechenaufgaben sehr anwendungsfreundlich ist, weil keine gesonderte Programmiersprache erlernt werden muss. Bei algebraischen Taschenrechnern weicht das Programmiermodell oft (aber nicht immer) von der manuellen Formeleingabe ab.

Nachteil der UPN ist in erster Linie die Tatsache, dass sie nicht aus dem täglichen Leben beziehungsweise der Schule vertraut ist und daher erst erlernt werden muss; hinzu kommt, dass die Vorteile erst beim intensiveren Gebrauch und vor allem bei der Arbeit mit komplizierten Formeln zu bemerken sind. Die Gewöhnung an eine der beiden Notationen kann den Umgang mit der jeweils anderen erschweren.

In der Vergangenheit, insbesondere in der Frühzeit elektronischer Taschenrechner, galt als wesentlicher Vorteil der UPN, dass sie sich mit geringerem Hardwareaufwand realisieren lässt. Es ist erwiesen, dass sich beliebig komplexe mathematische Berechnungen mit einem Stapel von nur vier Einträgen ausführen lassen; dadurch lässt sich ein vollwertiger UPN-Taschenrechner mit nur vier Stapelregistern bauen. Demgegenüber muss ein algebraischer Taschenrechner für jede Klammerebene und allgemein für jedes Zwischenergebnis („Punkt- vor Strichrechnung“), das er verarbeiten soll, ein eigenes Register besitzen; in der Praxis wurden algebraische Taschenrechner mit bis zu zwölf Operandenregistern zu Speicherung von bis zu elf unvollständigen Operationen hergestellt. Mit der Leistungsfähigkeit der heutigen elektronischen Schaltkreise ist dieser theoretische Vorteil der UPN technisch nicht mehr bedeutsam, und es werden heute moderne UPN-Taschenrechner mit mehr als vier Stapelregistern und mit zusätzlichen Speicherregistern ausgestattet.

Modelle

Es gibt im Vergleich zu rein algebraischen Taschenrechnern nur wenige Taschenrechnermodelle, die auch oder ausschließlich UPN unterstützen; der einzige bekannte Hersteller, der eine größere Zahl UPN-fähiger Geräte herstellt, ist Hewlett Packard. Mit Ausnahme des seit 1981 erhältlichen reinen UPN-Taschenrechners HP-12C und einiger rein algebraischer Geräte im unteren Preisbereich unterstützen die Anfang 2007 neu auf den Markt gekommenen HP-Taschenrechner wie der HP-50g beide Eingabenotationen.

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^[1]). Łukasiewicz stellte die polnische Notation als kompakte und klammerfreie Schreibweise für die Aussagenlogik vor.

Łukasiewicz weist selbst darauf hin,^[2] 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.

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 definiert wobei M und N beliebige Mengen sind:

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

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

$\sin:\mathbb{R}\to \mathbb{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:

$+:\mathbb{R} \times \mathbb{R}\rightarrow \mathbb{R};(x,y)\mapsto +(x,y)$.

Hier ist $\mathbb{R} \times \mathbb{R}$ die Menge aller reellen Zahlenpaare. Anstelle von x + y (Infixnotation) wird die Funktionsschreibweise + (x,y) (Präfix-Notation, polnische Notation) benutzt. Stellt man das + hinter die Klammern ((x,y) + ) erhält man die umgekehrte polnische Notation (Postfix-Notation) 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.

Quellen

1. ↑ „Die ältesten Texte in den ‚Selected Works‘, in denen Łukasiewicz polnische Notation verwendet, datieren relativ spät, sind aber Präsentationen vorangehender Arbeiten, die ‚in the course of the years 1920–1930‘ (Seite 131) stattgefunden haben, also auch keine genauere Zeitangabe geben.“ (Ch. Gottschall: Logische Notationen und deren Verarbeitung auf elektronischen Rechenanlagen aus theoretischer, praktischer und historischer Sicht (Diplomarbeit), Wien: 2005, Seite 88)
2. ↑ „On the history of the logic of propositions“, abgedruckt in: Łukasiewicz 1970

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

Weblinks

• Eine Einführung in die umgekehrte polnische Notation bei HP
• Postfix Notation – mini lecture (engl.)
• http://www.hpmuseum.org/rpn.htm Verwendung von RPN bei HP (engl.)