DSA 450 Notes

Problem Statement

Evaluate an arithmetic expression given as a string. The expression contains:

Non-negative integers
Operators: +, -, *, /
Parentheses: (, )
Spaces (which should be ignored)

Assume the expression is always valid.

Example:

Input: "3+2*2"
Output: 7

Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23

Input: "3+5 / 2"
Output: 5

Approach 1: Using Two Stacks (Operators and Operands)

Intuition

Use two stacks: one for operators and one for operands. Process operators based on precedence. Handle parentheses by treating them as precedence boundaries.

Algorithm

Scan expression from left to right
If digit: extract full number and push to operand stack
If '(': push to operator stack
If ')': evaluate until matching '('
If operator: evaluate operators with >= precedence, then push current operator
At end: evaluate remaining operators

java

import java.util.*;

public class ArithmeticEvaluator {
    private int precedence(char op) {
        if (op == '+' || op == '-') return 1;
        if (op == '*' || op == '/') return 2;
        return 0;
    }
    
    private int applyOp(int a, int b, char op) {
        switch(op) {
            case '+': return a + b;
            case '-': return a - b;
            case '*': return a * b;
            case '/': return a / b;
        }
        return 0;
    }
    
    public int evaluate(String expression) {
        Stack<Integer> operands = new Stack<>();
        Stack<Character> operators = new Stack<>();
        
        int i = 0;
        int n = expression.length();
        
        while (i < n) {
            char c = expression.charAt(i);
            
            // Skip spaces
            if (c == ' ') {
                i++;
                continue;
            }
            
            // If digit, extract the number
            if (Character.isDigit(c)) {
                int num = 0;
                while (i < n && Character.isDigit(expression.charAt(i))) {
                    num = num * 10 + (expression.charAt(i) - '0');
                    i++;
                }
                operands.push(num);
                continue;
            }
            
            // If opening parenthesis
            if (c == '(') {
                operators.push(c);
            }
            // If closing parenthesis
            else if (c == ')') {
                while (!operators.isEmpty() && operators.peek() != '(') {
                    int b = operands.pop();
                    int a = operands.pop();
                    char op = operators.pop();
                    operands.push(applyOp(a, b, op));
                }
                operators.pop(); // Remove '('
            }
            // If operator
            else {
                while (!operators.isEmpty() && operators.peek() != '(' &&
                       precedence(operators.peek()) >= precedence(c)) {
                    int b = operands.pop();
                    int a = operands.pop();
                    char op = operators.pop();
                    operands.push(applyOp(a, b, op));
                }
                operators.push(c);
            }
            
            i++;
        }
        
        // Apply remaining operators
        while (!operators.isEmpty()) {
            int b = operands.pop();
            int a = operands.pop();
            char op = operators.pop();
            operands.push(applyOp(a, b, op));
        }
        
        return operands.peek();
    }
    
    public static void main(String[] args) {
        ArithmeticEvaluator eval = new ArithmeticEvaluator();
        
        System.out.println("3+2*2 = " + eval.evaluate("3+2*2"));  // 7
        System.out.println("(1+(4+5+2)-3)+(6+8) = " + eval.evaluate("(1+(4+5+2)-3)+(6+8)"));  // 23
        System.out.println("3+5/2 = " + eval.evaluate("3+5/2"));  // 5
        System.out.println("10-2*3 = " + eval.evaluate("10-2*3"));  // 4
    }
}

Complexity Analysis

Time Complexity: O(n) - each character is processed once
Space Complexity: O(n) - stacks can hold up to n/2 operands and operators

Approach 2: Single Stack for +/- Only (Simpler Case)

Intuition

For expressions with only + and - (no precedence difference), use a single stack to store numbers with their signs.

Key Takeaways

Two stacks handle operator precedence elegantly - one for operands, one for operators
Process operators only when a higher/equal precedence operator is encountered
Parentheses create precedence boundaries - evaluate everything inside before continuing
The Shunting Yard algorithm (by Dijkstra) is the formal algorithm for this
Handle edge cases: spaces, multi-digit numbers, unary minus
For interview, be clear about operator precedence rules you're implementing

Arithmetic Expression evaluation

Problem Statement

Approach 1: Using Two Stacks (Operators and Operands)

Intuition

Algorithm

Complexity Analysis

Approach 2: Single Stack for +/- Only (Simpler Case)

Intuition

Key Takeaways