Umgekehrte Polnische Notation

Der Grundgedanke der Umgekehrten Polnischen Notation (UPN, auf englisch Reverse Polish Notation oder RPN) ist der, keine Klammern und keinen Vorrang von Operatoren zu benutzen. Einige der bekannten HP-Taschenrechner arbeiten nach diesem Prinzip, auch gibt es Programmiersprachen wie z.B. Forth, RPL oder PostScript, die diese Notation verwenden.

Bei der umgekehrt polnischen Notation werden zunächst die Operanden eingegeben und danach der darauf anzuwendende Operator.

Sehr leicht verständlich wird dieses Prinzip bei der Betrachtung der folgenden Formulierungen:

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").

Die übliche mathematische Notation heißt genau genommen Infix-Notation, UPN wird dann auch Postfix-Notation genannt.

Beispiel in der bekannten Notation: 3 + 4 * 5 = 3 + (4 * 5), weil die Multiplikation Vorrang vor der Addition hat.

Bei der UPN können solche Regeln entfallen, alle Operationen arbeiten mit den beiden oberen Elementen des Stack. Das Beispiel oben heißt in UPN: 3 4 5 * +

weiteres Beispiel: (3 + 4) * 5 in UPN: 3 4 + 5 *

Bei Operationen mit nur einem Operanden ist UPN sehr gebräuchlich - auch bei Rechnern, die sonst in 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.

Unter Anwendern wird häufig der Vorteil der UPN zur algebraischen Notation diskutiert. Nachteilig ist, dass man bei der UPN zunächst einmal die Anwendung lernen muss.

Die Vorteile liegen teilweise in der Implementierung in den Taschenrechnern (z.B. Konstantenautomatik, letzter berechneter Wert = LastX, umfangreiche Vertauschungsoperationen im Stack, Duplizierung von Werten = ENTER). Zu den verfahrensimmanenten Vorteilen zählt unter anderem, dass Zwischenergebnisse bei der manuellen Berechnung auf dem Taschenrechner immer angezeigt werden. Das Berechnungsbeispiel auf einem Taschenrechner sieht so aus: 4 Brötchen zu je 0,30 € plus 6 Brötchen zu je 0,45 € rechnet sich in UPN so:

4 ENTER 0,3 × (Zwischenergebnis 1,20 € sichtbar) 6 ENTER 0,45 × (Zwischenergebnis 2,70 € sichtbar) + Endergebnis 3,90 € sichtbar).

In algebraischer Notation werden die Zwischenergebnisse nicht angezeigt, sofern man keine Klammern eingibt.

Zur Geschichte

Die Polnische Notation (auch Präfix-Notation oder Lukasiewicz-Notation) verdankt ihren Namen dem polnischen Mathematiker Jan Lukasiewicz, der sie 1920 vorstellte.

Diese Notation, bei der der Operator vor den Operanden steht, bedarf keiner Klammerung, da die Präzedenz der Operationen eindeutig ist.

Der gleiche Effekt wird erreicht, wenn der Operand nicht vor den Operanden, sondern danach steht.

Diese Postfix-Notation wurde später ebenfalls von Lukasiewicz entwickelt und später als "Umgekehrte Polnische Notation" bezeichnet.

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, die seiner Stelligkeit entspricht und legt das Ergebnis der Operation wieder auf dem Stapel ab. Am Ende liegt dann das Ergebis des Terms oben auf dem Stapel.

Deshalb bildet die UPN die Grundlage für stapelbasierte Programmiersprachen wie Forth, RPL und PostScript.

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.)