Evaluate Postfix Expression in Java

In this article, we will look at how to evaluate a given Postfix expression to a result value. This is a problem related to Stack Data Structure. We will look at the algorithm with a step-by-step example along with the implementation in code. Let us first have a quick look at Postfix Expressions.

So, Postfix Expressions are the mathematical expressions where for each pair of Operator and Operands, the operators come after operands. Hence, the evaluation order is from left to right. Here operators are written after operands.

For example, XY+ is a Postfix Expression and its equivalent Infix is X+Y. Compilers generally use Postfix Notations to evaluate a given expression with ease without multiple scanning. It becomes easier to evaluate a given expression due to the order of operators and operands.

Now, Consider the Postfix Expression: 8 2 3 * + 7 / 1 – 

The Result after evaluation of this expression will be 1. At first, 2*3 = 6, its sum with 8 gives 14. 14 is then divided by 7 to give 2. After subtracting 1 with 2 we get 1 which is our result.

Note: The Postfix expression will be given as a String Input.

Postfix Evaluation Algorithm

We will use a Stack, the Stack will contain the Operands and the resultant value of each pair of operands for every operator. At the end of the algorithm, the Postfix stack will contain the resultant value obtained from the total expression.

• We traverse the whole String, for each character we encounter we have basically two cases to consider:
• If Character is an Operand: If the current character is an operand/Integer we push it into Stack.
• If Character is an Operator: If the current character is an operator we pop two operands from the Postfix stack evaluate the result with the respective operator and push the result back to Postfix Stack.
• We continue the above two steps for each such character. In the end, the Postfix stack will have only one value i.e. the final answer.

Example

Now, let’s understand the algorithm with a step-by-step example. We consider the same Postfix Expression: 8 2 3 * + 7 / 1 – .

Step 1:

We traverse the string (ignoring spaces) throughout its length from start(0) to End(Length – 1 = 9). At index = 0, we get 8 which is Integer/Operand so we push it into Postfix Stack. Similarly, at index = 1 and index = 2, we get 2 and 3 respectively which are also Operands so we push them into the stack. After these operations the Postfix Stack now looks like this:

Step 2:

We continue traversing and at index = 3, we get ‘ * ‘ an operator. This falls under Case 2 so we pop two items/Operands from the stack i.e. 3 and 2 and compute 3 * 2 = 6 and push the result back to stack. The Postfix stack now is:

Step 3:

Next at index = 4, we get ‘ + ‘ again an operator. So we again pop the two items compute the result 8 + 6 = 14 and push it back to stack again for future evaluation. Now at index = 5, we get 7 which is an operand so we push it into the stack. The stack now looks like this:

Step 4:

Moving again to the right at index = 6 we get, ‘ / ‘ an operator so we again pop the items 7 and 14 and compute the result 14 / 7 = 2, then push it to the stack. At index = 7, we get, 1 an integer so we simply push it into the stack.

Step 5:

Now, at index = 8, we get the ‘ – ‘ operator so we then pop the remaining elements from the stack and compute their result as 2 – 1 =1 and push it back to stack again. Finally, we reach the end of the string, and the Postfix Stack will have the only value which is the result of the total evaluation:

Note: We evaluate each pair of popped operands with the operator in reverse order to avoid errors in the result.

Implementation in Java

import java.util.*;

public class PostfixEvaluation
{

  static boolean isOperator(char ch)
  {
      if(ch == '+' || ch == '-' || ch == '*' || ch == '/')
      return true;
      
      return false;
  }
    
  static void evaluatePostfix(String exp)
  {
      Stack<Integer> postFix = new Stack<>();    // Create postfix stack
      int n = exp.length();
      
      for(int i=0;i<n;i++)
      {
        if(isOperator(exp.charAt(i)))
        {
        // pop top 2 operands.
        int op1 = postFix.pop();
        int op2 = postFix.pop();
              
        // evaluate in reverse order i.e. op2 operator op1.
        switch(exp.charAt(i))
        {
            case '+': postFix.push(op2 + op1);
                      break;
                      
            case '-': postFix.push(op2 - op1);
                      break;
                      
            case '*': postFix.push(op2 * op1);
                      break;
                
            case '/': postFix.push(op2 / op1);
                      break;
                    
        }
        
        }
        // Current Char is Operand simple push into stack
        else
        {
        // convert to integer
        int operand = exp.charAt(i) - '0';
        postFix.push(operand);
        }
      }
      
      // Stack at End will contain result.
      System.out.println(postFix.pop());
  }
  
  public static void main(String args[])
  {
      String exp = "823*+7/1-";
      System.out.print("The PostFix Evaluation for the Given Expression "+exp+" is: ");
      evaluatePostfix(exp);
  }
     
}

Output:

The PostFix Evaluation for the Given Expression 823*+7/1- is: 1

Time Complexity: We do a single traversal of the Given Postfix Expression throughout its length, so the Time Complexity is O(n), n is the length of Expression.

Space Complexity: We use a Stack which will at the most store all the Operands until we get an Operator so space complexity is O(T), T is the total number of operands in expression.

So that’s all about the article you can try out different examples with the algorithm discussed above and execute the code for a clear idea.