---

Aufgabe Reverse Polish Notation

Letzte Änderung: 29. June 2020, 10:47 Uhr
12 Punkte — im Detail
Ansicht:   |  

Die umgekehrte polnische Notation (Reverse Polish Notation, RPN) erlaubt es, die Auswertungsreihenfolge von arithmetischen Ausdrücken ohne Verwendung von Klammern festzulegen. Die Auswertung eines RPN-Ausdrucks ist außerdem verhältinismäßig leicht zu implementieren, da mit jedem eingelesenen Token entweder exakt ein Operand auf den Operandenstack gelegt wird oder exakt ein Operator ausgeführt wird. Das unterscheidet RPN von geklammerten Ausdrücken, bei denen die Auswertung eines geklammerten Audrucks aufgrund von Operatorpräzedenzregeln im schlimmsten Fall bis zur schließenden Klammer verzögert werden muss.

RPN wird noch heute in einigen Taschenrechnern verbaut. Das zugrundeliegende Konzept einer stackbasierten Rechenmaschine findet sich auch in anderen Gebieten der Informatik wieder.

Die Syntax ist wie folgt:
Zuerst werden die Operanden genannt, dann, durch ein Leerzeichen getrennt, der Operator zu den genannten Operanden.

Beispiel:

Mathematischer Ausdruck | Reverse Polish Notation
------------------------|------------------------
                     23 | 23
                 4 + 23 | 4 23 +
       511 * ( 4 + 23 ) | 511 4 23 + *
           511 * 4 + 3  | 511 4 * 23 +

Weitere Hinweise:

• Beachten Sie bei der Implementierung, dass bei der Auswertung von nicht-kommutativen Operatoren wie - oder / die Operandenreihenfolge wichtig ist.
• Wenn Ihr Parser negative Zahlen unterstützen soll, müssen Sie sich überlegen, wie Sie den Operator - und das negative Vorzeichen - unterscheiden.