Basic Calculator II — Stack-Based Expression Evaluation with Precedence

Problem Statement#

Given a string s which represents an expression, evaluate this expression and return its value. The integer division should truncate toward zero. You may assume that the given expression is always valid. All intermediate results will be in the range [-2^31, 2^31 - 1]. You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

s consists of only integers, the operators +, -, *, /, and spaces. Operators have standard precedence: * and / bind tighter than + and -.

Constraints:

• 1 <= s.length <= 3 * 10^5
• s represents a valid expression.
• Each integer is non-negative and fits in a 32-bit signed integer.

Input:  s = "3+2*2"
Output: 7
Explanation: 2*2 evaluates first, then 3+4 = 7.

Input:  s = " 3/2 "
Output: 1
Explanation: Integer division truncates toward zero.

Input:  s = " 3+5 / 2 "
Output: 5
Explanation: 5/2 = 2, then 3+2 = 5.

Why This Problem Matters#

LeetCode 227 Basic Calculator II is the most-asked stack-based parsing problem at Google, Amazon, Meta, and Uber. It tests three skills at once:

• Tokenizing: parsing characters into integers and operators while skipping whitespace.
• Operator precedence: handling * and / before + and - without using a parser generator.
• Truncating division: matching C-style truncation toward zero across positive and negative results.

This is the foundation for the harder Basic Calculator I (with parentheses), Basic Calculator III (parentheses + all four operators), and many real systems: SQL expression evaluators, spreadsheet formula engines, calculators in mobile apps, and shell arithmetic.

The Core Insight#

The trick is to keep a stack of "pending additive terms." Whenever you see a + or -, you push the next number with the appropriate sign. Whenever you see a * or /, you immediately combine it with the most recent value on the stack — this is how multiplication and division get to bind tighter than addition and subtraction.

At the end, the answer is the sum of all values on the stack.

The state machine looks like this:

1. Track prev_op (initialized to +).
2. Build the current number from successive digit characters.
3. When the next non-digit character (or end of string) is seen, "flush" the current number using prev_op:
   • +: push num.
   • -: push -num.
   • *: pop, multiply, push.
   • /: pop, integer-divide truncating toward zero, push.
4. Update prev_op to the new operator and reset num.

Sum of stack at the end is the answer. O(n) time, O(n) space.

A clever optimization removes the stack entirely by tracking just last_value and result — O(n) time, O(1) space — but the stack version is easier to extend to parentheses (LC 224 / 772).

Visual Dry Run#

Input: "3+5 / 2".

Sum = 3 + 2 = 5. Answer = 5.

Solution (Optimal)#

# Python — stack-based, O(n) time, O(n) space
def calculate(s: str) -> int:
    stack = []
    num = 0
    prev_op = '+'
 
    for i, ch in enumerate(s):
        if ch.isdigit():
            num = num * 10 + int(ch)
        if (not ch.isdigit() and ch != ' ') or i == len(s) - 1:
            if prev_op == '+':
                stack.append(num)
            elif prev_op == '-':
                stack.append(-num)
            elif prev_op == '*':
                stack.append(stack.pop() * num)
            elif prev_op == '/':
                # Python // floors toward -inf; we need truncation toward 0
                top = stack.pop()
                stack.append(int(top / num))
            prev_op = ch
            num = 0
 
    return sum(stack)

// JavaScript — stack-based, O(n) time, O(n) space
function calculate(s) {
    const stack = [];
    let num = 0;
    let prevOp = '+';
 
    for (let i = 0; i < s.length; i++) {
        const ch = s[i];
        if (ch >= '0' && ch <= '9') {
            num = num * 10 + (ch.charCodeAt(0) - 48);
        }
        if ((isNaN(parseInt(ch)) && ch !== ' ') || i === s.length - 1) {
            if (prevOp === '+') stack.push(num);
            else if (prevOp === '-') stack.push(-num);
            else if (prevOp === '*') stack.push(stack.pop() * num);
            else if (prevOp === '/') {
                const top = stack.pop();
                stack.push(Math.trunc(top / num));
            }
            prevOp = ch;
            num = 0;
        }
    }
 
    return stack.reduce((a, b) => a + b, 0);
}

# Python — O(1) space variant by collapsing additive terms incrementally
def calculateConst(s: str) -> int:
    result = 0
    last = 0
    num = 0
    prev_op = '+'
 
    for i, ch in enumerate(s):
        if ch.isdigit():
            num = num * 10 + int(ch)
        if (not ch.isdigit() and ch != ' ') or i == len(s) - 1:
            if prev_op == '+':
                result += last
                last = num
            elif prev_op == '-':
                result += last
                last = -num
            elif prev_op == '*':
                last *= num
            elif prev_op == '/':
                last = int(last / num)
            prev_op = ch
            num = 0
 
    return result + last

Complexity:

Common Mistakes#

1. Floor vs truncate division. In Python, 7 // -2 == -4 (floor), but the problem wants -3 (truncate). Use int(a / b) or int(operator.truediv(a, b)) or (a // b) if (a * b >= 0) else -(-a // b).

2. Forgetting to flush the last number. Without the i == len(s) - 1 guard, the final operand is never pushed.

3. Treating spaces as operators. Skip them explicitly. The not ch.isdigit() and ch != ' ' check is essential.

4. Multi-digit numbers parsed as single digits. Always use num = num * 10 + int(ch) to accumulate digits across multiple iterations.

5. Mixing up prev_op tracking. The operator we apply on flush is the previous operator, not the current character. The current character becomes the prev_op for the next flush.

Interview Tips#

• Begin by sketching the state machine: "I will scan once, build numbers digit by digit, and use a stack to defer additive operations and immediately resolve multiplicative ones."
• Discuss truncation vs floor division before coding. This is an easy one to miss: writing // in Python floors toward negative infinity and silently fails on negative results.
• After the stack version, offer the O(1)-space version as an optimization. Even if the interviewer says "stack is fine," they appreciate awareness.
• If asked about parentheses, explain that the stack approach extends naturally: when you see (, recurse or push state; when you see ), evaluate the inner expression.

Follow-up Questions#

1. Basic Calculator (LC 224). Adds parentheses but only + and -. Use a stack of partial sums.
2. Basic Calculator III (LC 772). All four operators plus parentheses. Combine the stack of LC 224 with the precedence handling of LC 227.
3. Add support for unary minus. Detect - after ( or at start as unary; handle by pushing 0 first.
4. Floating-point arithmetic. Replace int with float and handle precision concerns.
5. Right-to-left associativity. Some operators (like exponent) bind right-to-left; reverse scan or two-pass.

Key Takeaways#

• Use a stack to keep additive terms; multiplicative operators immediately combine with the top of the stack.
• Track prev_op and apply it when the next non-digit character arrives — flush logic must also fire at the end of the string.
• Watch out for truncation toward zero — Python // floors, which differs from C-style truncation on negative results.
• Stack version is O(n) space; the rolling-last version achieves O(1) space but is harder to extend.
• The technique generalizes to LC 224 (parentheses) and LC 772 (full calculator) by adding stack-of-state recursion.
• Real systems (SQL, spreadsheets, shell $(())) use the same pattern under the hood.