DSA 450 Notes

Problem Statement

Evaluate a postfix expression (Reverse Polish Notation). In postfix notation, operators come after their operands.

Postfix properties:

No parentheses needed
No precedence rules needed
Operands appear before their operators

Example:

Input: "2 3 1 * + 9 -"
Output: -4
Explanation: ((2 + (3 * 1)) - 9) = 2 + 3 - 9 = -4

Input: "100 200 + 2 / 5 * 7 +"
Output: 757
Explanation: ((100 + 200) / 2 * 5 + 7) = 150 * 5 + 7 = 757

Approach: Using Stack

Intuition

Scan the expression from left to right. Push operands onto stack. When an operator is encountered, pop two operands, apply the operator, and push the result back. The final value in the stack is the answer.

Algorithm

Create an empty stack
Scan expression from left to right:
- If operand: push to stack
- If operator: pop two operands, apply operator, push result
The only element in stack is the final result

java

import java.util.*;

public class PostfixEvaluation {
    public static int evaluatePostfix(String expression) {
        Stack<Integer> stack = new Stack<>();
        String[] tokens = expression.split(" ");
        
        Set<String> operators = new HashSet<>(Arrays.asList("+", "-", "*", "/"));
        
        for (String token : tokens) {
            if (operators.contains(token)) {
                int b = stack.pop();
                int a = stack.pop();
                
                int result;
                switch (token) {
                    case "+": result = a + b; break;
                    case "-": result = a - b; break;
                    case "*": result = a * b; break;
                    case "/": result = a / b; break;
                    default: result = 0;
                }
                
                stack.push(result);
            } else {
                stack.push(Integer.parseInt(token));
            }
        }
        
        return stack.peek();
    }
    
    // For single digit operands (no spaces)
    public static int evaluatePostfixSimple(String expression) {
        Stack<Integer> stack = new Stack<>();
        String operators = "+-*/";
        
        for (char c : expression.toCharArray()) {
            if (c == ' ') continue;
            
            if (operators.indexOf(c) != -1) {
                int b = stack.pop();
                int a = stack.pop();
                
                int result;
                switch (c) {
                    case '+': result = a + b; break;
                    case '-': result = a - b; break;
                    case '*': result = a * b; break;
                    case '/': result = a / b; break;
                    default: result = 0;
                }
                
                stack.push(result);
            } else if (Character.isDigit(c)) {
                stack.push(c - '0');
            }
        }
        
        return stack.peek();
    }
    
    public static void main(String[] args) {
        System.out.println("2 3 1 * + 9 - = " + evaluatePostfix("2 3 1 * + 9 -"));  // -4
        System.out.println("100 200 + 2 / 5 * 7 + = " + evaluatePostfix("100 200 + 2 / 5 * 7 +"));  // 757
        System.out.println("5 1 2 + 4 * + 3 - = " + evaluatePostfix("5 1 2 + 4 * + 3 -"));  // 14
        
        // Simple version
        System.out.println("231*+9- = " + evaluatePostfixSimple("231*+9-"));  // -4
    }
}

Complexity Analysis

Time Complexity: O(n) - each token is processed once
Space Complexity: O(n) - stack can hold up to n/2 operands

Infix to Postfix Conversion

To convert infix (normal notation) to postfix:

Key Takeaways

Postfix evaluation is simple - just use a stack for operands
Order matters: pop b first, then a; compute a op b
Postfix eliminates the need for precedence handling
Postfix is used internally by compilers and calculators
Converting infix to postfix uses the Shunting Yard algorithm
Each operator exactly consumes its two preceding operands