30% off Lifetime Premium Access expires December 2nd!

30% off Lifetime Premium Access expires Dec 2nd!

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Ask The Community

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Get Premium

Leetcode 224. Basic Calculator

Evaluate a string expression containing integers, '+', '-', parentheses and spaces (with unary '-' allowed) and return its numeric result without using eval. The core challenge is correctly handling nested parentheses and unary minus—typically solved with a stack or recursive parsing to maintain sign/state.

Asked at:

Flex

DESCRIPTION

Input:


s = "1 + 1"

Output:

Explanation: Simple addition: 1 + 1 = 2

Constraints:

1 <= s.length <= 3 * 10^5
s consists of digits, '+', '-', '(', ')', and ' '
s represents a valid expression
'+' is not used as a unary operation
'-' can be used as both binary and unary operation
There will be no two consecutive operators in the input
Every number and running calculation will fit in a signed 32-bit integer

Understanding the Problem

Let's trace through a concrete example: given the string '3+2*2', we need to evaluate it correctly.

If we just compute left-to-right, we'd get (3+2)*2 = 10, but that's wrong! The correct answer is 3+(2*2) = 7 because multiplication has higher precedence than addition.

Now consider '(1+(4+5+2)-3)+(6+8)'. We must handle nested parentheses correctly: innermost first (4+5+2)=11, then (1+11-3)=9, then (6+8)=14, finally 9+14=23.

Key constraints: The expression contains only digits 0-9, operators + and -, parentheses ( and ), and spaces. Unary minus is allowed (e.g., '-2+3' should return 1).

Edge cases: What about '- (3 + (4 + 5))' (unary minus before parentheses)? What about '1 - (-2)' (unary minus inside parentheses)? What about nested expressions like '((2))'?

Building Intuition

When we encounter a '(', we're starting a new sub-expression that must be evaluated independently. When we hit the matching ')', we've completed that sub-expression.

This creates a nested structure where inner expressions must be resolved before outer ones. The key insight: we need to remember the context (current sum and sign) when entering a sub-expression, then restore it when exiting.

Without parentheses, we could just scan left-to-right keeping a running sum. But parentheses create nested scopes where we must pause our current calculation, evaluate the inner part, then resume.

The most recently opened parenthesis must be matched with the next closing parenthesis we encounter - this 'last-in, first-out' pattern is crucial for handling arbitrary nesting depth.

Imagine evaluating '2 + (3 - (4 + 5))' step by step:

We're computing 2 + ... when we hit '(' - we need to pause and remember 'we were adding to 2'
Now computing 3 - ... when we hit another '(' - pause again and remember 'we were subtracting from 3'
Compute 4 + 5 = 9, hit ')' - resume the previous context: 3 - 9 = -6
Hit another ')' - resume the outermost context: 2 + (-6) = -4

We need a way to save and restore these contexts in reverse order of how we encountered them.

Common Mistakes

Forgetting to process the last number after the loop ends - the final number has no operator after it, so it must be added to the result after scanning completes

Not handling unary minus correctly at the start of the expression or after opening parentheses - need to initialize sign properly and detect when '-' is unary vs binary

Off-by-one errors when building multi-digit numbers - must accumulate digits correctly (num = num * 10 + digit) and reset num to 0 after processing

Incorrectly managing the stack for nested parentheses - must push BOTH the current result AND the sign before the parenthesis, then pop and combine them correctly when closing

Not handling spaces properly - must skip whitespace characters without breaking the parsing logic or accidentally treating them as number terminators

Optimal Solution

Use a stack to handle nested parentheses and maintain calculation state. Scan the string character by character, building numbers digit by digit. When we encounter an operator or parenthesis, process the previous number with its sign. For opening parentheses, push the current result and sign onto the stack (saving context). For closing parentheses, pop from the stack to restore the previous context and combine it with the sub-expression result. This naturally handles arbitrary nesting depth and unary minus.

def calculate(s):
    """
    Evaluate string expression with +, -, parentheses, spaces, and unary minus.
    Uses stack to handle nested parentheses and maintain calculation state.
    """
    # Initialize stack and variables
    stack = []
    current_number = 0
    current_result = 0
    sign = 1
    
    # Process each character
    for i, char in enumerate(s):
        # Build multi-digit numbers
        if char.isdigit():
            current_number = current_number * 10 + int(char)
        
        # Handle operators and parentheses
        elif char == '+':
            current_result += sign * current_number
            current_number = 0
            sign = 1
        
        elif char == '-':
            current_result += sign * current_number
            current_number = 0
            sign = -1
        
        elif char == '(':
            # Push current state to stack
            stack.append(current_result)
            stack.append(sign)
            # Reset for sub-expression
            current_result = 0
            sign = 1
        
        elif char == ')':
            # Complete current number
            current_result += sign * current_number
            current_number = 0
            # Pop sign and previous result
            current_result *= stack.pop()
            current_result += stack.pop()
            sign = 1
    
    # Add final number
    current_result += sign * current_number
    
    return current_result

Start calculating expression

0 / 51

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n) We scan through the string once, processing each character in constant time. Building numbers and stack operations are O(1) per character.

Space Complexity: O(n) In the worst case with deeply nested parentheses like '((((1))))' we need to store one context per nesting level on the stack, which can be O(n) in pathological cases.

What We've Learned

Stack for state preservation in nested contexts: Use a stack to save and restore sign and accumulated result when entering/exiting parentheses - the stack naturally handles nested scopes by pushing current state before '(' and popping to restore when encountering ')', making it perfect for expression evaluation with arbitrary nesting depth.
Sign propagation technique: Maintain a running sign variable that multiplies with the stack's top sign when processing operators - this elegantly handles both unary minus (like "-(3+5)") and sign changes through nested parentheses by treating signs as multiplicative state rather than trying to parse them structurally.
Character-by-character parsing with lookahead: Build multi-digit numbers by accumulating digits (num = num * 10 + digit) and only apply operations when hitting a non-digit operator or end of string - this avoids complex tokenization while correctly handling numbers of any length without splitting them prematurely.
Deferred operation pattern: Store the previous operator and only apply it when you encounter the next operator or closing parenthesis - this prevents off-by-one errors and naturally handles the last number in an expression without special-case logic at the end.
O(n) single-pass with O(n) space: The stack only stores state at parenthesis boundaries (not every character), making space proportional to nesting depth in practice, while the single left-to-right pass ensures linear time - this is optimal since you must read every character at least once.
Expression parser foundation: This stack-based state management pattern extends to building recursive descent parsers, AST evaluators, and formula engines in spreadsheets or calculators - understanding sign propagation and operator precedence handling here is fundamental to compiler design and expression evaluation systems.

Test Your Understanding

Why is stack the right data structure for this problem?

stack provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Late August, 2025

Flex

Mid-level

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More