# 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.

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`

The second element

Since 3 is an `operand` it should be pushed on the `stack`

The third element

Since 4 is an `operand` it should be pushed on the `stack`

The forth element

We now approach an `operator` (+).

This means that we pop off the first two elements on the `stack`, perform the `operator` on those two elements.

The fifth element

We now move the last element, which is an `operator`.

As before, we pop off the two elements from the stack and perform the `operator` on them.

The sixth element

We can see there is still an element on the stack. It is an `operand` so we pop it from the `stack`

Leaving us with 9 and an empty `stack`

At this point we are done!

# Conclusion:

A `stack` is a great way to evaluate a `Reverse Polish Notation` expression. This gives an automatic precedence, so there is no confusion on how expressions are evaluated. This is also very easy to calculate for machines.

Nice!

• Infix, Postfix and infix notation is covered HERE