Salfade logo

Evaluate a Postfix expression with the help of Stack Data Structure

Algorithms DataStructures Java Programming

Stack is a linear data structure which follows a particular order in which the operations are performed. The order is usually LIFO(Last In First Out).

The most common operations in stacks are

  • push  - add an element to the stack
  • pop - remove the top element from the stack
  • peek - read the value of the top element without popping it

uses of stack

  • Expression Handling ( prefix and postfix )
  • backtracking ( like undo )

Why do we need pre/post fix expressions?

Infix notation is easy to read for humans, whereas pre/post fix notation is easier to parse for a machine. The big advantage in pre/post fix notation is that there never arise any questions like operator precedence.

Evaluate a postfix expression

Let's consider a specific application of stack in this post. That is, Evaluating a postfix expression.

In the postfix expression the operator appears in the expression after the operands. Simply of the form (operand1 operand2 operator).

Example : A+BC = > (BC * ) A +

so first do multiplication of B and C , then add the result with A.

Algorithm to evaluate the postfix expression

  • Scan the expression from left to right
  • If you find an operand push it to stack
  • If you find an operator , use it to evaluate by popping two from the stack and push the result to the stack again.
  • Once you reach the end of the stack you should have only the value, that's the value of the expression

Lets get hands on it


Output of the above implementation

Evaluating expression 22*3+
2 * 2
3 + 4
result is 7

Evaluating expression 32*2+
2 * 3
2 + 6
result is 8

Evaluating expression 3*2+
postfix expression is not valid

Remarks on the implementation

It is assumed that the expression contains only a single character digit. But in a real world scenario the expression can contain two or more letter number, but again the algorithm is not going to change. But we can change the way of pushing things to the stack.

Related articles