Basic Calculator LeetCode 224 Guide

LeetCode 224 Basic Calculator asks you to implement a basic calculator that evaluates a mathematical expression given as a string. The expression may contain digits, the operators + and -, parentheses ( and ), and spaces. There are no multiplication or division operators, and no exponentiation — just addition and subtraction with arbitrarily nested parentheses. Your job is to return the integer result of evaluating the expression.

The input can be up to 3 * 10^5 characters long, ruling out any O(n^2) approach. The expression is always valid — no malformed input — and the intermediate results fit within a 32-bit signed integer. Despite the apparent simplicity of only two operators, the nested parentheses create a context-tracking challenge that cannot be solved by naive left-to-right scanning without extra bookkeeping.

Common examples include "1 + 1" (answer: 2), " 2-1 + 2" (answer: 3), and the more nuanced "(1+(4+5+2)-3)+(6+8)" (answer: 23). The last example requires correctly handling nested parentheses two levels deep, demonstrating that the algorithm must manage depth in a principled way rather than just scanning for balanced pairs.

The core difficulty of LeetCode 224 is that a minus sign before a parenthesis inverts the sign of every term inside — and that inversion can nest arbitrarily deep. Consider the expression "-(3-(4+5))". The outer minus negates the entire group. Inside, the second minus negates (4+5). The naive approach of evaluating left to right without tracking context would compute the wrong answer because it cannot account for the accumulated sign inversion from multiple nesting levels.

Simply counting parentheses depth or using a toggle flag is not sufficient. What you need is a way to remember the sign context that was in effect before you entered each opening parenthesis — and restore it when you exit the matching closing parenthesis. This is precisely what a stack is designed for: LIFO storage of context that needs to be restored when you unwind a recursive structure.

Recursive descent parsing is one valid solution, but it requires explicit recursion management. The iterative stack approach achieves the same effect without recursive function calls and handles the full depth of nesting allowed by the input constraints. The key insight is that the stack does not need to store the full expression — only the accumulated result and the sign before each opening parenthesis.

The algorithm maintains two key variables: result, which accumulates the running total for the current depth level, and sign, which is either +1 or -1 representing the sign of the next number to be added. Initially both are set to their identity values: result = 0 and sign = 1. A separate num variable accumulates the digits of the current multi-digit number as it is parsed character by character.

When the algorithm encounters an opening parenthesis, it pushes the current result and the current sign onto the stack, then resets result to 0 and sign to 1. This effectively saves the outer context and starts fresh for the inner expression. When a closing parenthesis is encountered, the inner result is finalized (any pending num is added), then the stack is popped to retrieve the saved sign and saved result. The inner result is multiplied by the saved sign and added to the saved result to produce the new current result.

This push-on-open, pop-on-close pattern mirrors exactly what recursive descent parsing does with the call stack. The iterative version just makes the stack explicit. Each pair of parentheses corresponds to exactly one push and one pop, so the stack depth equals the maximum nesting depth of the expression — in the worst case O(n) for a fully nested expression like ((((...)))).

Multi-digit numbers are parsed by accumulating digits into the num variable: each time a digit character is seen, num is updated as num = num * 10 + int(c). This left-shifts the existing digits by one decimal place and appends the new digit. The num variable is only committed to result when a non-digit character is encountered — either an operator (+/-) or a closing parenthesis. This means the algorithm naturally handles numbers of any length without needing a separate tokenization pass.

When a + or - operator is encountered, the pending num is added to result with the current sign: result += sign * num. Then num is reset to 0 and sign is updated to reflect the new operator (+1 for +, -1 for -). This deferred evaluation pattern — accumulate digits first, commit when operator is seen — is standard for expression parsers and correctly handles sequences like "12+34-56" without any lookahead.

Spaces are handled by doing nothing — simply skip any character that is a space. The space character has no semantic significance in this grammar, so the algorithm can safely ignore it. This keeps the main loop clean: the only characters that trigger action are digits (0-9), operators (+, -), and parentheses (( and )). Every other character, including spaces, falls through to a no-op.

Spaces are the simplest edge case — every space character is skipped with a continue or by falling through to the end of the loop body. The expression can have spaces between any tokens: "1 + 2", "( 1 + 2 )", or even multiple consecutive spaces. Because the algorithm only acts on digits, operators, and parentheses, spaces are automatically ignored without any special handling beyond the skip.

A leading minus sign like "-(1+2)" is handled correctly because the algorithm starts with sign = 1, and the minus at the start is processed as an operator before any digit: result += sign * num (which adds 0), then sign = -1. When the opening parenthesis is hit, result = 0 and sign = -1 are pushed. After evaluating (1+2) = 3 internally, the pop step computes 3 * (-1) + 0 = -3. Empty parentheses "()" would produce result = 0 inside, which correctly contributes 0 to the outer expression.

The most critical edge case is the last number in the string — the number at the very end has no trailing operator or closing parenthesis to trigger the num commit. This is why the final line after the loop must always be result += sign * num. Forgetting this step causes the last term to be silently dropped, producing incorrect results for any expression that ends with a number like "1+2" where the trailing 2 would be lost.

In Python, the solution is a single function evaluate(s: str) -> int. Initialize result = num = 0, sign = 1, stack = []. Iterate through each character. Digits update num. A + or - commits num to result then sets sign. An opening parenthesis pushes result and sign, resets both. A closing parenthesis commits num, then pops: result = result * stack.pop() + stack.pop(). After the loop, return result + sign * num. The entire body is about 15 lines. Time complexity is O(n) — each character is processed once. Space complexity is O(n) for the stack in the worst case of fully nested parentheses.

In Java, the solution uses a Deque<Integer> as the stack (ArrayDeque is preferred over Stack for performance). The character loop uses charAt(i) and Character.isDigit(c). Digits accumulate with num = num * 10 + (c - '0'). The operator branch uses result += sign * num then sign = (c == '+') ? 1 : -1. The opening parenthesis branch pushes result then sign. The closing parenthesis branch finalizes num, pops sign (cast to int from Integer), pops prevResult, computes result = result * sign + prevResult. After the loop, return result + sign * num.

Both implementations share the same algorithmic structure and achieve identical O(n) time and O(n) space. The Python version is slightly more concise thanks to duck typing and negative indexing, but the logic is a direct translation. A common interview extension is Basic Calculator II (LeetCode 227), which adds * and / — that version requires operator precedence handling and a different stack discipline where numbers are pushed with their sign and multiplication/division are applied immediately.

Basic Calculator II (LeetCode 227) extends this problem by adding multiplication and division. The approach shifts from a sign-context stack to a value stack where each number is pushed with its sign applied, and * and / are applied immediately to the top of the stack. Basic Calculator III (LeetCode 772) combines both — +/- with parentheses AND * / — requiring a unified approach that handles both operator precedence and grouping.

Valid Parentheses (LeetCode 20) is a simpler stack problem that checks bracket matching without any arithmetic. It is the foundation for understanding how stacks track paired delimiters. Evaluate Reverse Polish Notation (LeetCode 150) is the canonical stack-based expression evaluator where operator precedence is already encoded in the postfix order — no parentheses are needed because the RPN format encodes grouping implicitly.

Min Stack (LeetCode 155) and LFU Cache (LeetCode 460) are stack and data structure problems that exercise similar design skills — maintaining auxiliary state alongside primary state. The family of problems that use a stack to track context (monotonic stacks, parenthesis matching, expression evaluation) are among the most frequently tested patterns in technical interviews. Mastering the sign-tracking approach in LeetCode 224 is the gateway to all expression parser problems at the medium and hard level.