Reverse Polish Notation parser and calculator

There are different ways to represent arithmetic computations. The one we are used to makes use of infix notation, i.e. 1 + 2 + 3 – 5 = 1.

Some programming languages, most notably in the Lisp family, make use of prefix notation to form so-called S-Expressions, where the operation is placed first followed by the operands that it acts upon, e.g. (+ 2 3) yields 5, and you can read it as 2 + 3 in infix notation. Transforming the above example, we get (- (+ (+ 1 2) 3) 5). Here, the innermost + acts upon 1, 2, which gives 3. The outer plus takes this 3 and the other 3. This produces the sum 6, and the minus takes the inputs 6 and 5 from the resultant expression (- 6 5) and yields 1 by subtracting 5 from 6.

Therefore:

1. (- (+ (+ 1 2) 3) 5)
2. (- (+ 3 3) 5)
3. (- 6 5)
4. = 1

Yet other languages, such as concatenative languages including Forth and Factor, use postfix or Reverse Polish Notation (RPN), where the operator goes to the end, e.g. 10 5 + results in 10 + 5 = 15.
Following the first example, to convert it into RPN, we can write it as 5 1 2 + 3 + –

Here, it’s important to note that the model makes use of a stack. First, 5 is placed on the stack. Then, 1 and 2 are placed on the stack and +, a binary operation, takes those two values off the stack and produces 3, placing it back onto the stack. After this, 3 is placed on the stack, and the following plus operation takes the first 3 and the second 3 and adds them together to produce 6, placing it back on the stack. Finally, the minus operation subtracts the 5 we initially put on the stack from the 6, and puts that result onto the stack. The state of the stack can be shown as follows, after every operation:

1. Stack: [] (empty)
2. 5 put on the stack. Stack: [5]
3. 1 put on the stack. Stack: [5 1]
4. 2 put on the stack. Stack: [5 1 2]
5. + takes (2, 1) from the stack and produces 3. Stack: [5 3] (NB: 2 is taken first and then 1, in that order)
6. 3 put on the stack. Stack: [5 3 3]
7. + takes (3, 3) from the stack and produces 6. Stack: [5 6]
8. – takes (6, 5) from the stack and produces 1. Stack: [1]

Note that in the final step, 6 is at the “top” of the stack and is, therefore, the first operand in the operation. So, the expression is 6 – 5 and not 5 – 6.

You can find my implementation of Reverse Polish Notation here: https://github.com/LunarArcanus/RPN