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…

Image for post
Image for post
Photo by Lina Verovaya on Unsplash

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.

Image for post
Image for post

The first element

Since 2 is an operand it should be pushed on the stack

Image for post
Image for post

The second element

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

Image for post
Image for post

The third element

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

Image for post
Image for post

The forth element

We now approach an operator (+).

Image for post
Image for post

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

Image for post
Image for post

The fifth element

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

Image for post
Image for post

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

Image for post
Image for post

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

Image for post
Image for post

Leaving us with 9 and an empty stack

Image for post
Image for post

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!

Extend your knowledge

  • Infix, Postfix and infix notation is covered HERE

The Twitter contact:

Any questions? You can get in touch with me here

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store