Java Program to Evaluate Postfix Expression Using Stack

Introduction

Postfix notation, also known as Reverse Polish Notation (RPN), is a mathematical notation in which operators follow their operands. In this notation, there are no parentheses required to denote the precedence of operators, and the evaluation of the expression is straightforward when using a stack. This guide will walk you through writing a Java program that evaluates a postfix expression using a stack.

Problem Statement

Create a Java program that:

• Reads a postfix expression from the user.
• Uses a stack to evaluate the postfix expression.
• Displays the result of the evaluation.

Example:

• Input: Postfix expression: "23*54*+9-" (Equivalent to (2*3) + (5*4) - 9)
• Output: 17

Solution Steps

1. Create the Stack Structure: Define a Stack class or use the built-in Stack class to store operands during the evaluation.
2. Implement Postfix Evaluation:

• Traverse the postfix expression from left to right.
• For each operand, push it onto the stack.
• For each operator, pop the required number of operands from the stack, perform the operation, and push the result back onto the stack.

3. Display the Result: The result of the postfix expression will be the only value remaining on the stack after the entire expression has been processed.

Java Program

// Java Program to Evaluate Postfix Expression Using Stack
// Author: https://www.rameshfadatare.com/

import java.util.Stack;

public class PostfixEvaluator {

    // Method to evaluate a postfix expression
    public static int evaluatePostfix(String expression) {
        Stack<Integer> stack = new Stack<>();

        // Traverse through each character of the expression
        for (int i = 0; i < expression.length(); i++) {
            char ch = expression.charAt(i);

            // If the character is an operand, push it onto the stack
            if (Character.isDigit(ch)) {
                stack.push(ch - '0');  // Convert char to int
            } 
            // If the character is an operator, pop operands from the stack
            else {
                int operand2 = stack.pop();
                int operand1 = stack.pop();

                // Perform the operation and push the result back onto the stack
                switch (ch) {
                    case '+':
                        stack.push(operand1 + operand2);
                        break;
                    case '-':
                        stack.push(operand1 - operand2);
                        break;
                    case '*':
                        stack.push(operand1 * operand2);
                        break;
                    case '/':
                        stack.push(operand1 / operand2);
                        break;
                }
            }
        }

        // The final result will be the only element left in the stack
        return stack.pop();
    }

    public static void main(String[] args) {
        String expression = "23*54*+9-"; // Example postfix expression

        int result = evaluatePostfix(expression);
        System.out.println("The result of the postfix expression " + expression + " is: " + result);
    }
}

Explanation

Step 1: Initialize the Stack

• A stack is used to hold the operands during the evaluation process. The built-in Stack class in Java is used for this purpose.

Step 2: Traverse the Postfix Expression

• The postfix expression is traversed character by character.
• If the character is an operand (a digit), it is pushed onto the stack.
• If the character is an operator, the necessary number of operands are popped from the stack, the operation is performed, and the result is pushed back onto the stack.

Step 3: Perform Operations

• The operations handled in this program include addition (+), subtraction (-), multiplication (*), and division (/).
• For each operation, two operands are popped from the stack, the operation is performed, and the result is pushed back onto the stack.

Step 4: Return the Result

• After the entire postfix expression is processed, the final result will be the only element left in the stack. This result is then returned.

Output Example

The result of the postfix expression 23*54*+9- is: 17

Example with Different Postfix Expression

If you modify the postfix expression to "231*+9-" (Equivalent to (2 + (3 * 1)) - 9), the output will be:

The result of the postfix expression 231*+9- is: -6

Conclusion

This Java program demonstrates how to evaluate a postfix expression using a stack. By leveraging the stack data structure, the program efficiently handles the order of operations and computes the result of the expression without the need for parentheses or operator precedence rules. This exercise is valuable for understanding how to implement and manipulate stacks and how postfix notation simplifies expression evaluation in programming.