Reverse Polish Notation Parser

Reverse Polish notation (RPN), also known as Polish postfix notation or simply postfix notation, is a mathematical notation in which operators follow their operands. This notation is an alternative notation to the standard infix notation in which operators are located between their operands or to the prefix Polish notation (PN), in which operators precede their operands.

Note that the description “Polish” refers to the nationality of logician Jan Łukasiewicz, who invented Polish notation in 1924

Binary Expression Trees

The Polish Notations (prefix or postfix) are used by programming language interpreters where Boolean and arithmetic expressions are parsed into abstract syntax trees. You can find out more about the use of binary trees to store Boolean and arithmetic expressions and about the pre-order, in-order and post-order depth-first traversals of a binary tree.

The use of binary expression trees can be used to facilitate the conversion of an expression from a more intuitive infix notation to either a prefix (RPN) notation or postfix (PN) notation.

The Shunting-Yard Algorithm

Edsger W. Dijkstra invented the shunting-yard algorithm to convert infix expressions to postfix expressions (RPN). The name comes from the fact that the algorithm’s operation resembles that of a railroad shunting yard.

Why use the prefix notation or postfix notations?

The main benefit of both the Polish Notation and of the Reverse Polish Notation over the infix notation is that they do not require the use of parentheses as long as each operator has a fixed number of operands.

For instance:

As a result, entering an expression using the Polish Notations (PN or RPN) is quicker and would lead to less errors even though it may appear less intuitive to start with than the infix notation.

The reverse Polish scheme was first introduced in 1954 by Arthur Burks, Don Warren, and Jesse Wright and was later on reinvented by Friedrich L. Bauer and Edsger W. Dijkstra in the early 1960s in order to reduce computer memory access by using a stack to evaluate a RPN expression.

Using a Stack to evaluate a RPN expression

The following Python code demonstrated the use of a Stack data structure to evaluate/parse an expression using the Reverse Polish Notation.

You can retrace the steps from this algorithm using the following arithmetic expressions: