Evaluation of Postfix Expression

Last Updated on September 13, 2022 by Gokul Kannan

Arithmetic Expression

An Arithmetic expression is a finite combination of arithmetic operands, operators and brackets. The common way of representing an arithmetic expression is by using infix notation. In infix notation, the operands are separated by an operator.

For example:

1. X + Y.
2. (X + Y) – Z.
3. X / Y

The infix notation is solved using the operator precedence rule.

Operator precedence table:

Example: (4 + 5) (8 / 4 – 2) 9 (1 – 2) 9 * -1 -9

We can also represent an arithmetic expression using prefix or postfix notation.

Postfix Notation

As the name suggests, post means after, hence in postfix notation the operator comes after the operators in the expression. In the postfix expression, we don’t use brackets. The prefix notation is commonly known as Reverse Polish notation.

Example: Pretfix: NM-XY+ Infix: (X + Y) (M – N)

Algorithm to evaluate prefix notation using stack:

1. Read the expression from left to right.
2. If the current character is an operand, push it to the stack.
3. If the current character is an operator, remove the top two characters from the stack. Let’s say the removed characters are operand1 and operand2. Now. evaluate (operand1 operator operand2) and push the solution back to the stack.
4. The last character in the stack after traversing the complete prefix notation will be the solution.

Dry run:

Implementation:

import java.util.*;
public class Prepbytes
{
	public static void main(String[] args) {
		char expression[] = new char[]{'2', '3', '+', '4', '5', '-', '*'};
		int ans = evaluate(expression);
		System.out.println(ans);
	}
	
	// This function will evaluate the given expression
	public static int evaluate(char[] expression) {
	    Stack<Character> st = new Stack<>();
	    
	    // Traverse the given expression in left to right direction
	    for(char ch : expression){
	        
	        // If the current character is an operand, push it to the stack.
	        if((int)ch - '0' >= 0 && (int)ch - '0' <= 9) {
	            st.push(ch);
	        }
	        
	        // If the current character is an operator.
	        else{
	            
	            // Remove the top two characters from the stack.
	            int operand2 = st.pop() - '0';
	            int operand1 = st.pop() - '0';
	            int val = 0;
	            
	            // Evaluate (operand1 operator operand2)
	            switch(ch) {
	                case '+':
	                    val = operand1 + operand2;
	                    break;
                    case '-':
                        val = operand1 - operand2;
	                    break;
                    case '*':
                        val = operand1 * operand2;
	                    break;
                    case '/':
                        val = operand1 / operand2;
	                    break;
	            }
	            
	            // Push the solution back to the stack.
	            st.push((char)(val + '0'));
	        }
	    }
	    return st.pop() - '0';
	}
}

Output: -5

Time complexity: O(n) where n is the number of characters in the expression. Each character is pushed and popped in the stack exactly once, hence the time complexity is O(n).

Space complexity: O(n) as we are using stack.

This article tried to discuss how to evaluate a postfix expression. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE | Competitive Programming at Prepbytes.