Umgekehrte Polnische Notation: Eine elegante Alternative zur Auswertung mathematischer Ausdrücke
Die umgekehrte polnische Notation (UPN) ist eine effiziente Methode zur Auswertung mathematischer Ausdrücke, die dadurch gekennzeichnet ist, dass Operatoren nach ihren Operanden platziert werden. Dieser Ansatz ermöglicht das Weglassen von Klammern, was den Berechnungsprozess vereinfacht und verdeutlicht. Auch wenn es anfangs ungewohnt erscheinen mag, beschleunigt die Verwendung von UPN die Ausführung von Operationen erheblich, insbesondere in Computersystemen und programmierbaren Taschenrechnern.
Es gibt zahlreiche Möglichkeiten, mathematische Ausdrücke zu schreiben. Die gebräuchlichste ist die Infixnotation, bei der Operatoren zwischen Operanden stehen, wie z. B. A + B oder (C D) - E. Diese Notation mag uns Menschen zwar intuitiv erscheinen, ist aber nicht unbedingt die optimalste Lösung für Computer und Taschenrechner. In diesem Artikel werden wir eine weniger bekannte, aber wohl elegantere Alternative untersuchen: die umgekehrte polnische Notation (UPN), auch bekannt als Postfixnotation.
Was ist die umgekehrte polnische Notation?
UPN ist eine mathematische Notation, bei der Operatoren auf ihre Operanden folgen. Anstatt A + B zu schreiben, notieren wir dies in UPN als A B +. Es mag auf den ersten Blick ungewöhnlich erscheinen, aber ihre Vorteile werden schnell deutlich.
Das Konzept der UPN stammt von dem polnischen Mathematiker Jan Łukasiewicz, der in den 1920er Jahren die Präfixnotation (polnische Notation) entwickelte, bei der Operatoren ihren Operanden vorangestellt werden. Die Postfixnotation ist eine Variation davon, die in den 1950er Jahren von dem australischen Informatiker Charles Hamblin weiterentwickelt wurde, um die Computerverarbeitung zu vereinfachen.
Warum ist UPN nützlich?
Die Hauptvorteile der UPN sind die Beseitigung von Mehrdeutigkeiten und die Recheneffizienz. Die Infixnotation erfordert Klammern, um die Reihenfolge der Operationen zu verdeutlichen, und Computer benötigen komplexe Parsing-Algorithmen, um die Operatorpräzedenz korrekt zu verarbeiten. In der UPN hingegen sind Klammern unnötig, und die Reihenfolge der Operationen wird automatisch durch die Struktur des Ausdrucks bestimmt.
Dies war besonders wichtig für frühe Computer und Taschenrechner, bei denen die Hardwareressourcen begrenzt waren. Taschenrechner, die UPN verwenden, konnten Berechnungen einfacher und schneller durchführen.
Historische Randnotiz: Die UPN-Notation wurde erstmals in den 1960er und 70er Jahren von Hewlett-Packard (HP) populär gemacht. Der Tischrechner HP-9100A (1968) war einer der ersten kommerziell erhältlichen Rechner, der UPN verwendete. Später verwendete auch der legendäre HP-35 (1972), der erste wissenschaftliche Taschenrechner, UPN, und diese Methode wurde für lange Zeit zu einem Markenzeichen der professionellen Taschenrechner von HP. UPN-Taschenrechner waren bekannt für ihre schnellen und genauen Berechnungen und erfreuten sich großer Beliebtheit bei Ingenieuren, Wissenschaftlern und Finanzexperten.
Wie UPN funktioniert
Betrachten wir ein Beispiel dafür, wie UPN funktioniert. Betrachten Sie den Infix-Ausdruck: (3 + 4) 2 - 5.
Zuerst wandeln wir diesen in UPN um. Für die Umwandlung müssen wir die Reihenfolge der Operationen berücksichtigen. In diesem Fall führen wir zuerst die Addition innerhalb der Klammern aus, multiplizieren dann mit zwei und subtrahieren schließlich fünf. Der UPN-Ausdruck lautet: 3 4 + 2 5 -.
Sehen wir uns nun an, wie man diesen UPN-Ausdruck mit Hilfe eines Stacks auswertet. Ein Stack ist eine Datenstruktur, in die Elemente eingefügt (push) und entfernt (pop) werden können, wobei immer das zuletzt eingefügte Element zuerst entnommen wird (LIFO - Last-In, First-Out).
Schrittweise Auswertung des UPN-Ausdrucks:
3: Lese3. Es ist ein Operand, lege ihn auf den Stack (push). Stack-Zustand:[3]4: Lese4. Auch ein Operand, lege ihn auf den Stack (push). Stack-Zustand:[3, 4]+: Lese den Operator+. Nimm zwei Operanden vom Stack (pop) (zuerst4, dann3). Führe die Addition aus:3 + 4 = 7. Lege das Ergebnis (7) wieder auf den Stack (push). Stack-Zustand:[7]2: Lese2. Operand, lege ihn auf den Stack (push). Stack-Zustand:[7, 2]: Lese den Operator. Nimm zwei Operanden vom Stack (pop) (zuerst2, dann7). Führe die Multiplikation aus:7 2 = 14. Lege das Ergebnis (14) wieder auf den Stack (push). Stack-Zustand:[14]5: Lese5. Operand, lege ihn auf den Stack (push). Stack-Zustand:[14, 5]-: Lese den Operator-. Nimm zwei Operanden vom Stack (pop) (zuerst5, dann14). Führe die Subtraktion aus:14 - 5 = 9. Lege das Ergebnis (9) wieder auf den Stack (push). Stack-Zustand:[9]
Da wir das Ende des UPN-Ausdrucks erreicht haben und sich nur noch ein Element auf dem Stack befindet, ist dieses Element das Endergebnis. Der Wert des Ausdrucks (3 + 4) 2 - 5, der in UPN ausgewertet wurde, ist also 9.
Wie man Infix-Ausdrücke in UPN umwandelt?
Der gebräuchlichste Algorithmus zur Umwandlung von Infix-Ausdrücken in UPN ist der Shunting-yard-Algorithmus, der von Edsger Dijkstra entwickelt wurde. Dieser Algorithmus verwendet einen Stack (für Operatoren und Klammern) und eine Ausgabewarteschlange (die in der Praxis einfach eine Liste sein kann) für die Umwandlung.
Schritte des Shunting-yard-Algorithmus:
- Tokenisierung: Zerlege den Infix-Ausdruck in Tokens (Zahlen, Operatoren, Klammern).
- Initialisierung: Erstelle einen leeren Stack zur Speicherung von Operatoren und eine leere Ausgabewarteschlange zum Aufbau des UPN-Ausdrucks.
- Verarbeitung von Tokens: Iteriere durch die Tokens:
- Zahl: Wenn das Token eine Zahl ist, füge es der Ausgabewarteschlange hinzu.
- Operator (op1): Wenn das Token ein Operator ist:
- Solange sich ein Operator (op2) oben auf dem Stack befindet UND entweder:
- op2 eine höhere Priorität als op1 hat, ODER
- op2 die gleiche Priorität wie op1 hat UND op1 linksassoziativ ist (in unserem Beispiel sind alle Operatoren linksassoziativ),
- Nimm op2 vom Stack (pop) und füge ihn der Ausgabewarteschlange hinzu.
- Lege op1 auf den Stack (push).
- Solange sich ein Operator (op2) oben auf dem Stack befindet UND entweder:
- Linke Klammer
(: Lege sie auf den Stack (push). - Rechte Klammer
):- Solange der Operator oben auf dem Stack keine linke Klammer ist:
- Nimm den Operator vom Stack (pop) und füge ihn der Ausgabewarteschlange hinzu. (Wenn der Stack leer wird, bevor eine linke Klammer gefunden wird, liegt ein Fehler vor.)
- Wenn sich eine linke Klammer oben auf dem Stack befindet, nimm sie vom Stack (pop) (füge sie aber nicht der Ausgabewarteschlange hinzu - Klammern sind nicht im UPN-Ausdruck enthalten).
- Wenn der oberste Stack-Eintrag nach der Verarbeitung der rechten Klammer keine linke Klammer ist, dann sind die Klammern nicht paarweise zusammenpassend.
- Solange der Operator oben auf dem Stack keine linke Klammer ist:
- Leere den Stack: Wenn keine Tokens mehr zu lesen sind, nimm alle verbleibenden Operatoren vom Stack (pop) und füge sie der Ausgabewarteschlange hinzu.
- Ergebnis: Die Ausgabewarteschlange enthält nun den UPN-Ausdruck.
Präzedenz und Assoziativität:
Das Verständnis von Operatorpräzedenz und Assoziativität ist wichtig. Die übliche Reihenfolge der Präzedenz (von höchster zu niedrigster):
- Multiplikation (
), Division (/) - Addition (
+), Subtraktion (-)
Alle vier grundlegenden arithmetischen Operationen sind linksassoziativ, d. h. Operatoren mit der gleichen Präzedenz werden von links nach rechts ausgewertet (z. B. a - b - c = (a - b) - c).
Beispiel für die Umwandlung von Infix (3 + 4) 2 - 5 in UPN mit dem Shunting-yard-Algorithmus:
| Token | Ausgabewarteschlange | Operator-Stack | Bemerkung |
|---|---|---|---|
( | ( | Linke Klammer auf den Stack gelegt. | |
3 | 3 | ( | Zahl zur Ausgabewarteschlange hinzugefügt. |
+ | 3 | (, + | Operator auf den Stack gelegt. |
4 | 3, 4 | (, + | Zahl zur Ausgabewarteschlange hinzugefügt. |
) | 3, 4, + | ( | Rechte Klammer: Operatoren (+) in die Warteschlange verschieben, bis linke Klammer gefunden wird. Linke Klammer entfernen. |
| 3, 4, + | | Operator auf den Stack gelegt (Stack war leer). |
2 | 3, 4, +, 2 | | Zahl zur Ausgabewarteschlange hinzugefügt. |
- | 3, 4, +, 2, | - | Operator: - auf den Stack legen. |
5 | 3, 4, +, 2, 5 | - | Zahl zur Ausgabewarteschlange hinzugefügt. |
| Ende | 3, 4, +, 2, 5, - | Ende der Eingabe: Verbleibende Operatoren (-) vom Stack in die Warteschlange verschieben. |
Somit lautet die UPN-Form des Infix-Ausdrucks (3 + 4) 2 - 5: 3 4 + 2 * 5 -.
Zusammenfassung
Die umgekehrte polnische Notation ist eine elegante und effiziente Methode zum Schreiben und Auswerten mathematischer Ausdrücke. Auch wenn sie auf den ersten Blick weniger intuitiv erscheint als die Infixnotation, bietet UPN mehrere Vorteile, insbesondere für die Computerverarbeitung. Sie beseitigt Mehrdeutigkeiten, benötigt keine Klammern und kann effizient mit einem einfachen Stack ausgewertet werden. Der Shunting-yard-Algorithmus bietet eine weit verbreitete und effektive Methode zur Umwandlung von Infix-Ausdrücken in UPN.
Ihre historische Bedeutung ist unbestreitbar, da sie eine wichtige Rolle in frühen Taschenrechnern spielte, und sie ist auch heute noch ein relevantes Konzept in der Informatik, das in Compilern und virtuellen Maschinen verwendet wird. Obwohl sie im Alltag weniger gebräuchlich ist, ist UPN ein wertvolles Werkzeug und eine Denkweise, die einen tieferen Einblick in die Beziehung zwischen mathematischen Ausdrücken und Computeroperationen ermöglicht.