Understanding stacks with Dijkshtra’s two stack algorithm for arithmetic expression evaluation

Data structure is simply a collection of data. It is organized in such a way that, it is easy for us to store, access and modify the information. There are different types of data structures like arrays, stacks, queue, linked list, binary tree etc,.

Stack is a data structure based on last in first out policy.  It is analogous to stack of plates or stack of files or books. Just like whichever book is kept on top is taken out first, whatever data we added recently will be retrieved first.

A very good example of stacks in real time is back button implementation in browser. Whenever we click hyperlinks, the previous page address is stored in stack. When back button is clicked, the most recent address is popped out.

Other examples include implementing undo button in any editor, organizing emails, checking for parenthesis in a compiler etc,.

Stack is a very popular form of abstract data type used in modern programming language. It is “abstract” because all the details are hidden from us . We are not bothered about how functions are implemented, where the data is stored etc,. We just invoke the functions and make use of it.

Basic operations in stack are –

Push() – push new element into the top of the stack.

Pop() – Most recent element from the top of the stack is popped out.

isEmpty() – returns true if stack is empty

size() – returns number of elements in the stackp.

A few languages allow the use of peek() function wherein you can find the value of top most element without popping it out.

Dijkstra’s two stack algorithm –

Take an arithmetic expression like this –

(5 + (3 * 8) ) – (2*7)

Without use of stacks, it is quite challenging to evaluate an arithmetic expression like this. In 1960, Dijkstra came up with a very simple algorithm to evaluate arithmetic expression with the help of two stacks.

You should declare two stacks – values stack and operator stack. Read the expression character by character and do the following.

  1. If number, push it into values stack
  2. If operator, push it into operator stack
  3. Ignore left parenthesis
  4. when right parenthesis is encountered, pop operator and corresponding number of values and perform the operation. Then push the result into values stack.

At the end, the result will be available in values stack.

In order to focus on the algorithm and lets assume the following to avoid unnecessary logic for handling the input

1. Each token is separated by space. Token here represents either the parenthesis or the number or the operator.

2. Each expression is entered within parenthesis and the parenthesis are perfectly balanced.

Eg ( 3 * 4 ) + 5 is invalid ( ( 3 * 4 ) + 5 ) is valid. Note space between each entry or token.