Expression Evaluation (Calculator Problems)

The Problem

Given a string like "3 + 2 * 4 - 1", evaluate it and return the result. This sounds straightforward until you remember that multiplication and division have higher precedence than addition and subtraction, so you cannot just evaluate left to right. The expression 3 + 2 * 4 - 1 equals 10, not 19, because the 2 * 4 must be computed before the additions and subtractions.

This family of problems appears on LeetCode as Basic Calculator (224), Basic Calculator II (227), and Basic Calculator III (772). Each variant adds a layer of complexity, but they all build on the same core ideas.

The Simplest Case: Basic Calculator II

Take Basic Calculator II (LeetCode 227), which handles +, -, *, and / but no parentheses. The key insight is to separate the operators into two tiers by precedence. Multiplication and division are high precedence, so they should be applied immediately. Addition and subtraction are low precedence, so they can be deferred.

The algorithm uses a stack of numbers. We also track the "pending operator," the operator that appeared just before the current number. As we parse each number:

• If the pending operator is +, push the number onto the stack.
• If the pending operator is -, push the negated number onto the stack.
• If the pending operator is *, pop the top of the stack, multiply it by the current number, and push the result back.
• If the pending operator is /, pop the top, divide (truncating toward zero), and push back.

After processing all characters, sum the entire stack. The additions and subtractions were deferred by pushing positive or negative values; the multiplications and divisions were resolved immediately by modifying the stack top.

Walking Through "3 + 2 * 4 - 1"

Let us trace through the expression step by step. We initialize pending_op = '+' (so the first number gets pushed as-is).

• Parse the number 3. Pending op is +, so push 3. Stack: [3]. Update pending op to +.
• Parse the number 2. Pending op is +, so push 2. Stack: [3, 2]. Update pending op to *.
• Parse the number 4. Pending op is *, so pop 2, compute 2 * 4 = 8, push 8. Stack: [3, 8]. Update pending op to -.
• Parse the number 1. Pending op is -, so push -1. Stack: [3, 8, -1].
• Sum the stack: 3 + 8 + (-1) = 10.

The multiplication was handled immediately when we saw 4 (the second operand of *). The addition and subtraction were deferred by pushing their operands with appropriate signs, then collected at the end with a single sum.

Code: Basic Calculator II

def calculate_ii(s: str) -> int:
    stack = []
    num = 0
    pending_op = '+'
    for i, c in enumerate(s):
        if c.isdigit():
            num = num * 10 + int(c)
        if c in '+-*/' or i == len(s) - 1:
            if pending_op == '+':
                stack.append(num)
            elif pending_op == '-':
                stack.append(-num)
            elif pending_op == '*':
                stack.append(stack.pop() * num)
            elif pending_op == '/':
                stack.append(int(stack.pop() / num))
            pending_op = c
            num = 0
    return sum(stack)

Notice the condition i == len(s) - 1: this ensures we process the very last number even if the string does not end with an operator. The int(stack.pop() / num) handles Python's truncation-toward-zero requirement for integer division (since Python's // truncates toward negative infinity, which gives wrong results for negative numbers in this context).

Adding Parentheses: Basic Calculator I

Basic Calculator I (LeetCode 224) handles +, -, and parentheses, but no * or /. At first glance parentheses seem like they require a completely different approach, but the insight is elegant: parentheses create a sub-expression. When you encounter (, you save your current running result and current sign onto the stack, then start fresh with a new result of 0 and sign of +1 inside the parentheses. When you encounter ), you finish the sub-expression, pop the saved sign and saved result, and combine them.

Think of it this way: 1 + (2 - (3 + 4)) is really saying "compute whatever is inside the parentheses, then add it to 1." Inside those parentheses, you encounter another set of parentheses, so you recursively save state, compute the inner expression, and restore.

Walking Through "1 + (2 - (3 + 4))"

We maintain result (the running total at the current nesting level), sign (the sign of the next number), and a stack for saved state.

• Read 1. result = 0 + 1*1 = 1.
• Read +. sign = +1.
• Read (. Push current result (1) and sign (+1) onto stack. Reset result = 0, sign = +1. Stack: [1, 1].
• Read 2. result = 0 + 1*2 = 2.
• Read -. sign = -1.
• Read (. Push result (2) and sign (-1) onto stack. Reset result = 0, sign = +1. Stack: [1, 1, 2, -1].
• Read 3. result = 0 + 1*3 = 3.
• Read +. sign = +1.
• Read 4. result = 3 + 1*4 = 7.
• Read ). Pop sign = -1 and saved_result = 2 from stack. result = 2 + (-1)*7 = 2 - 7 = -5. Stack: [1, 1].
• Read ). Pop sign = +1 and saved_result = 1. result = 1 + 1*(-5) = 1 - 5 = -4. Stack: [].

The answer is -4, which matches 1 + (2 - 7) = 1 + (-5) = -4.

Code: Basic Calculator I

def calculate_i(s: str) -> int:
    result = 0
    sign = 1
    num = 0
    stack = []
    for c in s:
        if c.isdigit():
            num = num * 10 + int(c)
        elif c == '+':
            result += sign * num
            num = 0
            sign = 1
        elif c == '-':
            result += sign * num
            num = 0
            sign = -1
        elif c == '(':
            stack.append(result)
            stack.append(sign)
            result = 0
            sign = 1
        elif c == ')':
            result += sign * num
            num = 0
            result = stack.pop() * result + stack.pop()
    result += sign * num
    return result

When we hit ), we first fold in the last pending number, then pop the saved sign (multiply) and saved result (add). The order of pops matters: sign was pushed second, so it comes out first.

Combining Everything: Full Calculator with All Operators and Parentheses

Basic Calculator III (LeetCode 772) supports +, -, *, /, and parentheses. This is the most general version, and it requires combining the ideas from both simpler variants.

The Recursive Approach

The cleanest way to handle this is with recursion. The idea is that every parenthesized group is a self-contained sub-expression. When you encounter (, you recursively evaluate the sub-expression inside, get back a number, and use that number just as you would use any other operand. The recursive function itself uses the Basic Calculator II logic (stack-based, processing * and / immediately and deferring + and -). The only addition is: when you see (, recurse; when you see ), return from the current level.

A practical way to implement this is with an index pointer that all recursive calls share. The outer call starts at index 0. When it encounters (, it advances past it and calls itself. The inner call processes characters until it hits the matching ), advances past it, and returns both the computed value and the updated index. The outer call then continues from where the inner call left off.

def calculate_iii(s: str) -> int:
    def helper(index: int) -> tuple[int, int]:
        stack = []
        num = 0
        pending_op = '+'
        while index < len(s):
            c = s[index]
            if c.isdigit():
                num = num * 10 + int(c)
            elif c == '(':
                num, index = helper(index + 1)
            if c in '+-*/)' or index == len(s) - 1:
                if pending_op == '+':
                    stack.append(num)
                elif pending_op == '-':
                    stack.append(-num)
                elif pending_op == '*':
                    stack.append(stack.pop() * num)
                elif pending_op == '/':
                    stack.append(int(stack.pop() / num))
                pending_op = c
                num = 0
                if c == ')':
                    break
            index += 1
        return sum(stack), index

    result, _ = helper(0)
    return result

When we encounter (, we recurse to evaluate the sub-expression, and the returned num is treated as if we had just parsed a regular number. When we encounter ), we break out of the loop and return, and the caller will pick up right after the closing parenthesis. This naturally handles arbitrary nesting.

The Shunting-Yard Algorithm

For fully general expression parsing, especially when you have many levels of precedence, right-associative operators, or function calls, Dijkstra's shunting-yard algorithm is the standard tool. It converts infix expressions to postfix (reverse Polish notation) using an operator stack, then evaluates the postfix expression with a value stack. The algorithm handles precedence and associativity through a comparison rule: before pushing a new operator, pop and apply all stacked operators of greater-or-equal precedence.

For interview purposes, the recursive approach above is usually simpler and sufficient. The shunting-yard algorithm is worth knowing conceptually, but implementing it correctly under time pressure is tricky, and interviewers rarely expect it.

Complexity Analysis

All three calculator variants run in $O(n)$ time, where $n$ is the length of the input string. Each character is visited exactly once (in the recursive version, each character is processed by exactly one level of recursion). The space complexity is $O(n)$ in the worst case: the stack can grow to hold $O(n)$ entries if the expression is something like 1 + 2 + 3 + ... + n (all deferred additions), and the recursion depth can be $O(n)$ for deeply nested parentheses like (((...))).

The common thread across these problems is the separation of concerns by precedence. Low-precedence operations are deferred (pushed onto a stack). High-precedence operations are resolved immediately (applied to the stack top). Parentheses reset the context by creating a sub-problem, either via an explicit stack save/restore or via recursion. Once you internalize this framework, any calculator variant becomes a matter of plugging in the right pieces.

Recognizing this pattern

You're probably looking at expression evaluation when:

• The input is a string containing +, -, *, / and possibly parentheses or unary operators.
• The problem asks for the numeric result of a textual arithmetic expression.
• Operator precedence matters: * and / bind tighter than + and -.
• You need to parse infix, postfix (RPN), or prefix notation and produce a value.

Common templates:

• Single-stack with deferred sign: track a running number and the previous operator, applying it when you hit the next operator. Example: Basic Calculator II.
• Parentheses via sign stack or recursion: push the current sign/result on (, pop and combine on ). Example: Basic Calculator.
• Full precedence with parens: combine the deferred-operator trick with recursion or a parenthesis stack. Example: Basic Calculator III.
• Reverse Polish evaluation: push numbers, pop two and apply on operators. Example: Evaluate Reverse Polish Notation.