Postfix evaluation in java

Hi coders! In this tutorial, we are going to discuss a very important topic that is generally skipped by the learners, the topic is postfix notation. Postfix notation represents algebraic expressions. As postfix is an operation of stack it does not need parenthesis. Most of thee complex algebraic expression can be easily solved with the help of postfix notation. So let’s start learning postfix evaluation in Java.

Method to perform postfix in Java

  • First of all, just create a stack that can store the values and operands of the expression.
  • Check each expression one by one. If the element is a number then push it into the stack, if the element is an operator then evaluate the operator on the values and pop all of them and push the result into the stack.
  • After the end of the expression, the final result will be left in the stack.

Let us take an example to understand it in a better way:

Suppose the given expression is like:  “4 3 2 * + 11 -“.

  1. Firstly 4 is a value so it will be directly stored in the stack similarly, 3 and 2 will be stored in the stack.
  2. When ” * ” will come 3 and 2 will be multiplied and result 6 will get stored in the stack.
  3. ” + ” will be scanned and the remaining values in the stack will get added i.e. 4+6 = 10 which will be stored in the stack.
  4. Value 11 will come and will be stored in the stack as it is.
  5.  when  “-” will be scanned it will be evaluated with the values in the stack and the result will be stored in the stack ads 10 – 11 = 1.
  6. Hence, the final result of the expression will be ” -1 “.

Program to perform postfix evaluation in Java

 

import java.util.*; 
  
public class PostfixEval  
{ 
 /* function which will evaluate value of a  given postfix expression */ 
   protected  static int evalPostfix(String express) 
    { 
        Stack<Integer> st = new Stack<>(); 
          
        for(int i=0; i < express.length(); i++) /* loop to scan all elements of the expression one by one */
        { 
            char ch = express.charAt(i); 
             
            if(Character.isDigit(ch)) /* pushing value into the stack */
            st.push(ch - '0'); 
              
           
            else       /* if the operator comes it will be evaluated */
            { 
                int value1 = st.pop(); 
                int value2 = st.pop(); 
                  
                switch(ch) 
                { 
                    case '+': 
                    st.push(value2 + value1); 
                    break; 
                      
                    case '-': 
                    st.push(value2 - value1); 
                    break; 
                        
                    case '*': 
                    st.push(value2*value1); 
                    break; 
                    case '/': 
                    st.push(value2/value1); 
                    break; 
              } 
            } 
        } 
        return st.pop();   // result return  
    } 
      
    // Driver function
    public static void main(String[] args)  
    { 
      String express="432*+11-"; 
      System.out.println("Postfix evaluation of the given expression comes out to be :" +evalPostfix(express)); 
    } 
} 

// code is provided by Anubhav Srivastava
Output:

Postfix evaluation of the given expression comes out to be : -1.

 

Hence, the time complexity comes out to be O(n) since only once the expressions are scanned.

I coded only for four operators since the expression has only four expression but if there are other different expression then more cases can be added in the code accordingly.

Hope, you like the tutorial.

ALso read:

Leave a Reply

Your email address will not be published. Required fields are marked *