Parsing Expressions

The commitments we take on keeps growing for ever. A stack is how your mind remembers to circle back.

How does a computer understand 3 + (2 * 5)? It can't just read left-to-right; it needs to respect the order of operations, with parentheses taking highest priority. A stack is the perfect data structure for this task!

Before reading on, try to solve this problem. How would you check if a string of parentheses is "balanced"?

Problem: Valid Parentheses (LeetCode Link): Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. 💡 Hint

The key is to use a stack. When you see an opening bracket, you push it onto the stack. When you see a closing bracket, you check if the top of the stack is its matching opening bracket. If it is, you pop the stack. If it's not, or if the stack is empty, the string is invalid.

This "last-in, first-out" (LIFO) behavior is the core pattern for parsing. The stack naturally handles the nested structure of expressions—the last thing you opened is the first thing you must close.

Level 1: Just the Structure (Validating Parentheses)

This is the simplest form of parsing. We only care about the structural symbols ((, [, {) and ignore everything else.

Define matching pairs: Use a map like { ')':'(', '}':'{', ']':'[' }, or even a switch statement.
Single Pass:
- If you see an opening bracket, push it to the stack.
- If you see a closing bracket, check if the stack is empty or if its top doesn't match. If so, it's invalid. Otherwise, pop.
Final Check: After the loop, the stack must be empty for the string to be valid.

def is_valid_parentheses(s: str) -> bool:
    stack = []
    mapping = {")": "(", "}": "{", "]": "["}

    for char in s:
        if char in mapping.values():  # Opening bracket
            stack.append(char)
        elif char in mapping:  # Closing bracket
            if not stack or mapping[char] != stack.pop():
                return False
    return not stack

public boolean isValidParentheses(String s) {
    Stack<Character> stack = new Stack<>();
    Map<Character, Character> mapping = new HashMap<>();
    mapping.put(')', '(');
    mapping.put('}', '{');
    mapping.put(']', '[');

    for (char c : s.toCharArray()) {
        if (mapping.containsValue(c)) { // Opening bracket
            stack.push(c);
        } else if (mapping.containsKey(c)) { // Closing bracket
            if (stack.isEmpty() || mapping.get(c) != stack.pop()) {
                return false; // Mismatch or empty stack
            }
        }
    }
    return stack.isEmpty();
}

bool isValidParentheses(const std::string& s) {
    std::stack<char> stack;
    std::unordered_map<char, char> mapping = {
        {')', '('},
        {'}', '{'},
        {']', '['}
    };

    for (char c : s) {
        if (mapping.count(c) == 0) { // Opening bracket
            stack.push(c);
        } else { // Closing bracket
            if (stack.empty() || mapping[c] != stack.top()) {
                return false; // Mismatch or empty stack
            }
            stack.pop();
        }
    }
    return stack.empty();
}

Level 2: Simple Arithmetic (No Parentheses)

Now, let's evaluate an expression like 3 - 2 * 5. We need to respect that multiplication and division have higher precedence than addition and subtraction.

A clever way to handle this is with a stack and the "deferred addition, immediate multiplication" trick. We process the expression, but only add numbers to the stack. If we see a * or /, we immediately apply it to the last number we added to the stack.

State Variables: Keep track of the current_number being built and the last_operator seen (default to +).
Process: Iterate through the string. When you hit an operator (or the end of the string):
- Apply the last_operator to the current_number.
- If last_operator was + or -, just push the current_number (or -current_number) to the stack.
- If last_operator was * or /, pop the last value from the stack, multiply/divide it by current_number, and push the result back.
Final Result: The sum of all numbers in the stack is the answer.

Problem: Basic Calculator II (LeetCode Link): Given a string s which represents a basic expression, implement a calculator to evaluate it.

def calculate_simple(s: str) -> int:
    stack = []
    num = 0
    last_op = '+'
    s += '+' # This helps us to avoid a final check for the last number

    for char in s:
        if char.isdigit():
            num = num * 10 + int(char)
        elif char in "+-*/":
            if last_op == '+':
                stack.append(num)
            elif last_op == '-':
                stack.append(-num)
            elif last_op == '*':
                stack.append(stack.pop() * num)
            elif last_op == '/':
                stack.append(int(stack.pop() / num))
            last_op = char
            num = 0
            
    return sum(stack)

public int calculateSimple(String s) {
    Stack<Integer> stack = new Stack<>();
    int num = 0;
    char lastOp = '+';
    s = s + "+"; // This helps us to avoid a final check for the last number

    for (char c : s.toCharArray()) {
        if (Character.isDigit(c)) {
            num = num * 10 + (c - '0');
        } else if ("+-*/".indexOf(c) != -1) {
            if (lastOp == '+') stack.push(num);
            else if (lastOp == '-') stack.push(-num);
            else if (lastOp == '*') stack.push(stack.pop() * num);
            else if (lastOp == '/') stack.push(stack.pop() / num);
            lastOp = c;
            num = 0;
        }
    }
    int result = 0;
    while(!stack.isEmpty()) result += stack.pop();
    return result;
}

int calculateSimple(string s) {
    stack<int> st;
    long num = 0;
    char lastOp = '+';
    s += '+'; // This helps us to avoid a final check for the last number

    for (char c : s) {
        if (isdigit(c)) {
            num = num * 10 + (c - '0');
        } else if ("+-*/".indexOf(c) != -1) {
            if (lastOp == '+') st.push(num);
            else if (lastOp == '-') st.push(-num);
            else if (lastOp == '*') {
                int top = st.top(); st.pop();
                st.push(top * num);
            } else if (lastOp == '/') {
                int top = st.top(); st.pop();
                st.push(top / num);
            }
            lastOp = c;
            num = 0;
        }
    }
    int res = 0;
    while (!st.empty()) {
        res += st.top();
        st.pop();
    }
    return res;
}

Level 3: Putting it Together (Handling Parentheses)

Now, let's combine the two ideas to solve expressions like 3 * (2 + 5). The trick is to treat everything inside parentheses as a sub-problem.

When you see (, push the current state onto a stack. You can think of it as "pausing" the current evaluation until you find the matching ).
Since we saved the current state, reset the working state:
- Reset num = 0; and lastOp = '+';.
When you see ), pop the stack to continue evaluation from where you left off.
- When you see ), do the validations we discussed earlier for parentheses.

This solution beautifully combines both #1 and #2 we discussed above. Anything inside parentheses is evaluated as a sub-expression, and the stack allows you to handle nested structures naturally.

Problem: Basic Calculator (LeetCode Link): This problem focuses on +, -, and parentheses.

You can also use recursion to solve this problem, but the stack-based approach is more efficient and straightforward for parsing expressions.

def evaluate_expression(s):
    expression_stack = []
    context_stack = []  # To store state of calculation when we hit '('

    num = 0
    last_op = '+'

    for i, c in enumerate(s):
        if c.isdigit():
            num = num * 10 + int(c)  # Build the current number

        elif c == '(':
            # Save the current context, start fresh
            context_stack.append((expression_stack, last_op))
            expression_stack = []  # Start a new fresh context
            num = 0
            last_op = '+'

        elif c == ')':
            # Finish off the inner expression
            apply_operation(expression_stack, last_op, num)
            inner_value = sum(expression_stack)

            # Restore the previous context
            expression_stack, last_op = context_stack.pop()
            num = inner_value

        elif c != ' ':
            # If we hit an operator or end of string, process the last number
            apply_operation(expression_stack, last_op, num)

            # Update the last operator and reset num
            last_op = c
            num = 0
    
    # Final processing of the last number
    apply_operation(expression_stack, last_op, num)
    return sum(expression_stack)

def apply_operation(stack, last_op, num):
    if last_op == '+':
        stack.append(num)
    elif last_op == '-':
        stack.append(-num)
    elif last_op == '*':
        stack[-1] *= num
    elif last_op == '/':
        # Integer division
        stack[-1] = int(stack[-1] / num)

public int evaluateExpression(String s) {
    Stack<Integer> expressionStack = new Stack<>();
    Stack<Object[]> contextStack = new Stack<>(); // To store state of calculation when we hit '('

    int num = 0;
    char lastOp = '+';

    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);

        if (Character.isDigit(c)) {
            num = num * 10 + (c - '0'); // Build the current number
        } else if (c == '(') {
            // Save the current context, start fresh
            contextStack.push(new Object[]{expressionStack, lastOp});
            expressionStack = new Stack<>(); // Start a new fresh context
            num = 0;
            lastOp = '+';
        } else if (c == ')') {
            // Finish off the inner expression
            applyOperation(expressionStack, lastOp, num);
            int innerValue = 0;
            while (!expressionStack.isEmpty()) {
                innerValue += expressionStack.pop();
            }

            // Restore the previous context
            Object[] context = contextStack.pop();
            expressionStack = (Stack<Integer>) context[0];
            lastOp = (char) context[1];
            num = innerValue;
        } else if (c != ' ') {
            // If we hit an operator, process the last number
            applyOperation(expressionStack, lastOp, num);

            // Update the last operator and reset num
            lastOp = c;
            num = 0;
        }
    }

    // Final processing of the last number
    applyOperation(expressionStack, lastOp, num);
    int result = 0;
    while (!expressionStack.isEmpty()) {
        result += expressionStack.pop();
    }
    return result;
}

private void applyOperation(Stack<Integer> stack, char lastOp, int num) {
    if (lastOp == '+') {
        stack.push(num);
    } else if (lastOp == '-') {
        stack.push(-num);
    } else if (lastOp == '*') {
        stack.push(stack.pop() * num);
    } else if (lastOp == '/') {
        stack.push(stack.pop() / num);
    }
}

// Helper function to apply operations
void applyOperation(std::stack<int>& s, char lastOp, int num) {
    if (lastOp == '+') {
        s.push(num);
    } else if (lastOp == '-') {
        s.push(-num);
    } else if (lastOp == '*') {
        int prev = s.top();
        s.pop();
        s.push(prev * num);
    } else if (lastOp == '/') {
        int prev = s.top();
        s.pop();
        s.push(prev / num);
    }
}

int evaluateExpression(const std::string& expr) {
    std::stack<int> expressionStack;
    std::stack<std::pair<std::stack<int>, char>> contextStack; // To store state of calculation when we hit '('

    long long num = 0;
    char lastOp = '+';

    for (int i = 0; i < expr.length(); ++i) {
        char c = expr[i];

        if (isdigit(c)) {
            num = num * 10 + (c - '0'); // Build the current number
        } else if (c == '(') {
            // Save the current context, start fresh
            contextStack.push({expressionStack, lastOp});
            expressionStack = std::stack<int>(); // Start a new fresh context
            num = 0;
            lastOp = '+';
        } else if (c == ')') {
            // Finish off the inner expression
            applyOperation(expressionStack, lastOp, num);
            int innerValue = 0;
            while (!expressionStack.empty()) {
                innerValue += expressionStack.top();
                expressionStack.pop();
            }

            // Restore the previous context
            std::pair<std::stack<int>, char> context = contextStack.top();
            contextStack.pop();
            expressionStack = context.first;
            lastOp = context.second;
            num = innerValue;
        } else if (c != ' ') {
            // If we hit an operator, process the last number
            applyOperation(expressionStack, lastOp, num);

            // Update the last operator and reset num
            lastOp = c;
            num = 0;
        }
    }

    // Final processing of the last number
    applyOperation(expressionStack, lastOp, num);
    int result = 0;
    while (!expressionStack.empty()) {
        result += expressionStack.top();
        expressionStack.pop();
    }
    return result;
}

Bonus Point: The Shunting-Yard Algorithm

For a truly generic and powerful solution, look up Dijkstra's Shunting-Yard Algorithm. It's a method for parsing expressions specified in infix notation. It can handle operator precedence and associativity (e.g., (2^3)^4 vs 2^(3^4)).

The algorithm works by converting the infix expression (like 3 + 4 * 2) into a postfix expression (like 3 4 2 * +), also known as Reverse Polish Notation (RPN). Postfix expressions are trivial to evaluate with a single stack. While it's more complex than the methods above, understanding it provides a deep insight into how compilers and calculators work. It's rarely expected in an interview unless you're aiming for a compiler or language design role, but knowing it exists is a huge plus.