Member-only story
Evaluate Reverse Polish Notation using a Stack
You can use Stacks to work out RPN. Really.
You might be wondering how to calculate Reverse Polish Notation. You might also be surprised how easy it is when you use a stack.
Read on and find out…
Difficulty: Beginner | Easy | Normal | Challenging
Prerequisites:
- Some understanding of a stack (guide HERE)
- Some understanding of Reverse Polish Notation (guide HERE)
Terminology
Operand: The value on which an operator is performed
Operator: A symbol like minus that shows an operation
Reverse Polish Notation (RPN): A mathematical notation in which operators follow operands
Stack: A data structure used to store objects
The algorithm
Stacks can be used to evaluate postfix notation equations (also known as Reverse Polish notation).
So the algorithm moves along the expression, pushing each operand on the stack while operators cause two items to be popped off the stack, evaluated and the result pushed back on the stacks.
This can be tricky to understand. Therefore I’ve prepared an example for you:
Evaluating Reverse Polish Notation (RPN) with a Stack — The Example
We will evaluate the expression by moving from the left to the right of our expression. In this case we will evaluate + 2 + 3 4.
We take the first element on the left of the expression. We also have a stack that is initially empty.
The first element
Since 2 is an operand it should be pushed on the stack
