Evaluation of Postfix expression

  Problem Statement - Given a string of postfix expression, You have to evaluate value of given postfix expression.

Background-As a human we always deal with infix expression. For example 5+4*(6-2). Here our calculation step will be as following:

5+4*(6-2) -> 5+4*4 -> 5+16=21.

But unfortunately computer system doesn't understand infix expression. To evaluate infix expression computer system first convert it to prefix or postfix expression. (We may cover how to convert infix expression to  prefix and postfix expression and vice versa in some other tutorial based on users feedback.)

Below is the postfix expression of above example:

5+4*(6-2) -> 5+4*62-  -> 5+462-* = 5462-*+

Solution - First we will understand it by an example. 

We are taking an postfix expression 5462-*+ mentioned in above section for our understanding. Below is the steps how an post fix expression is evaluated.

1. First we scan the string left to right till first encounter of an operation symbol. In our case it is "-" symbol.

2. Based on nature of operation like unary, binary etc., we go back and select same number of operands(In case of unary select one operand, In case of binary 2 operands ). 

3. Process that part of expression like operand1 operation operand2

In our example "-" is the first occurance of operation and it is a binary operation nd its 2 previous operands are 2 and 6. so part 62- will be processed first(6-2) and result will be stored at same place as below.

Next * is the binary operation and 2 operands are 4,4 so it will be processed as below:

Selection of Data Structure:

In above example we every time we are depending upon operands which are last appearing in string sequence. And operation of the result performed on operand are stored at last position. If we try to remember such data structure where operation is performed on last inserted symbol then it is Stack data structure. We can solve this problem with the stack as given below:

Above image shows the processing of input postfix expression, which is described below:

1. In Fig 1 input string is scanned from left to right. During scanning all operands are pushed onto the stack.
2. In process of the scanning of string symbols once we encounter any operation symbol based of the nature of operation (like unary or binary etc.) required number of operands from stack is popped and operation is performed on popped operands. Result of operation is again pushed back to operand stack. 
3. In our example in Fir 2 first we encounter symbol "-" which is binary operator. Accordingly we pop two operands 2 and 6 where operand1=6 and operand2=2. so result=6-2=4. Here 4 again pushed back to the operand stack.
4. Same as step 2 and 3, next symbol in input string "*" is processed in Fig 3 and "+" symbol is processed in Fig 4. And finally result 21 is achieved.

Now we will write algorithm for mentioned problem statement based on above stack example.

evaluatePostfixExpression(inputStr)

{

1. Create operand stack S
2. For i=1 to length(inpurStr)
3.        char ch=inpurStr[i]
4.       if(isNumber(ch))
5.               S.push(ch)
6.        else
7.              operator=ch
8.               operand2=S.pop()
9.               operand1=S.pop()
10.              tempResult=operand1 operator operator2
11.             S.push(tempResult)
12. return S.pop()

}

Below is the JAVA code implementation of above algorithm.

import java.io.*;

import java.util.Stack;

public class PostFixOperationEval {

/**

 * @param args

 * @throws IOException 

 */

public static void main(String[] args) throws IOException {

// TODO Auto-generated method stub

 BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        String inputStr=br.readLine();

                 

        

        int result=evaluatePostfixExpression(inputStr);

       System.out.println("Evaluated result="+result); 

}

private static int evaluatePostfixExpression(String inputStr) {

// TODO Auto-generated method stub

Stack<Integer> stack=new Stack<Integer>();

        int operand1,operand2,temp;

      for (int i = 0; i < inputStr.length(); i++) {

char ch=inputStr.charAt(i);

switch(ch)

{

case '+':

operand2=stack.pop();

operand1=stack.pop();

temp=operand1+operand2;

stack.push(temp);

break;

case '-':

operand2=stack.pop();

operand1=stack.pop();

temp=operand1-operand2;

stack.push(temp);

break;

case '*':

operand2=stack.pop();

operand1=stack.pop();

temp=operand1*operand2;

stack.push(temp);

break;

case '/':

operand2=stack.pop();

operand1=stack.pop();

temp=operand1/operand2;

stack.push(temp);

break;

default:

temp=ch-'0';

stack.push(temp);

break;

}

}  

return stack.pop();

}

}