Skip to content
LeetCode Solutions

Basic Calculator

Problem Statement

Section titled “Problem Statement”

Implement a calculator to evaluate a string expression containing:

  • Digits and multi-digit numbers
  • Operators: +, -, *, /
  • Parentheses for grouping: (, )
  • Whitespace (ignore it)

Return the integer result. Integer division truncates toward zero.

Examples

Section titled “Examples”
InputOutputExplanation
"1 + 1"2Simple addition
" 2-1 + 2 "3Basic arithmetic with spaces
"(1+(4+5+2)-3)+(6+8)"23Nested parentheses: (1+11-3)+(14) = 9+14
"2*(5+5*2)/3+(6/2*5)"17Mixed operators: 2*(15)/3+(15) = 10+15 (left-to-right)

Constraints

Section titled “Constraints”
  • 1 <= s.length <= 3 * 10^5
  • s consists of digits, '+', '-', '*', '/', '(', ')', and ' '.
  • All integers in the expression are non-negative.
  • Integer division truncates toward zero.
  • There will not be any division by zero.
  • Valid expressions only (no invalid syntax).

Real-World Applications

Section titled “Real-World Applications”

Complexity Comparison

Section titled “Complexity Comparison”
ApproachTimeSpaceParsingSuited For
Stack with SignO(n)O(d)Single passEasier to understand, only +/-
Two-Pass (Postfix)O(n)O(n)Infix → Postfix → EvalAll operators, full precedence

d = nesting depth (typically much less than n)

Which approach should you learn first?

Section titled “Which approach should you learn first?”
  • Pick Stack with Sign if you want a simple, intuitive solution (good for interviews).
  • Pick Two-Pass if you need to handle all operators and understand compiler design.
Most Intuitive
Stack with Sign
O(n) time · O(d) space
Most Flexible
Two-Pass Postfix
O(n) time · O(n) space
Section titled “Approach 1: Stack with Sign (Recommended)”
★ Recommended

For simple + and -, we can use a stack to handle parentheses. The key insight is:

  • Accumulate numbers as we read digits.
  • When we encounter an operator or closing paren, decide what to do with the number.
  • Push partial results onto a stack when we enter parentheses; pop and combine when we exit.

The “sign” variable tracks whether the next number should be added or subtracted.

⏱ Time O(n) Single pass 💾 Space O(d) Stack depth = nesting

Step-by-step Example

Section titled “Step-by-step Example”

Input: "(1+(4+5+2)-3)+(6+8)"

StepCharnumsignresultstackAction
0—010[]Initialize
1(010[0, 1]Push result & sign
21110[0, 1]Accumulate digit
3+111[0, 1]Apply sign, reset
4(011[0, 1, 1, 1]Push nested context
5-84+5+211112[0, 1, 1, 1]Sum → 4+5+2 = 11
9)11112[0, 1]Pop sign & prev; 1 + (1*12)
10-0-112[0, 1]Subtract next
1133-19[0, 1]Apply sign → 12 - 3
12)3-19[]Pop and combine
13+019[]Add next group
14(019[9, 1]Push context
15-176+814114[9, 1]Sum → 6+8 = 14
18)14123[]Pop and finalize

Animated walkthrough

How the stack solution handles operators and parentheses

Watch the stack grow and shrink as we enter and exit parentheses. Track sign changes at each + or - operator.

Step 1 of 7 Target: 23
Waiting to begin...
Array state
Memory / lookup state

Pseudocode

Section titled “Pseudocode”
function basicCalculatorStack(s):
    stack = []
    num = 0
    sign = 1
    result = 0


    for char in s:
        if char is digit:
            num = num * 10 + int(char)
        else if char in "+-":
            result += sign * num
            sign = 1 if char == '+' else -1
            num = 0
        else if char == '(':
            stack.push(result)
            stack.push(sign)
            result = 0
            sign = 1
        else if char == ')':
            result += sign * num
            sign = stack.pop()
            prevResult = stack.pop()
            result = prevResult + sign * result
            num = 0


    return result + sign * num

Solution Code

Section titled “Solution Code”
basic_calculator_stack.py
def basic_calculator_stack(s: str) -> int:
    """
    Evaluate a mathematical expression with +, -, *, /, and parentheses.


    Approach: Recursive stack-based parser
    - Use helper function to parse expression level (handles + and -)
    - Use another helper to parse term level (handles * and /)
    - Parentheses trigger recursive parsing of nested sub-expressions
    - This respects operator precedence naturally: term > expression


    Time: O(n) - single pass through string
    Space: O(d) - recursion depth equals nesting level
    """
    if not s:
        return 0


    def parse_number(s, i):
        """Extract a number starting at index i."""
        while i < len(s) and s[i].isspace():
            i += 1
        num = 0
        while i < len(s) and s[i].isdigit():
            num = num * 10 + int(s[i])
            i += 1
        return num, i


    def parse_factor(s, i):
        """Parse a factor: number or (expression)."""
        while i < len(s) and s[i].isspace():
            i += 1


        if s[i] == '(':
            i += 1  # Skip '('
            result, i = parse_expression(s, i)
            while i < len(s) and s[i].isspace():
                i += 1
            i += 1  # Skip ')'
            return result, i
        else:
            return parse_number(s, i)


    def parse_term(s, i):
        """Parse multiplication and division (higher precedence)."""
        result, i = parse_factor(s, i)


        while i < len(s):
            while i < len(s) and s[i].isspace():
                i += 1
            if i >= len(s) or s[i] not in '*/':
                break


            op = s[i]
            i += 1
            operand, i = parse_factor(s, i)


            if op == '*':
                result *= operand
            else:  # op == '/'
                result = int(result / operand)


        return result, i


    def parse_expression(s, i):
        """Parse addition and subtraction (lower precedence)."""
        result, i = parse_term(s, i)


        while i < len(s):
            while i < len(s) and s[i].isspace():
                i += 1
            if i >= len(s) or s[i] not in '+-':
                break


            op = s[i]
            i += 1
            operand, i = parse_term(s, i)


            if op == '+':
                result += operand
            else:  # op == '-'
                result -= operand


        return result, i


    result, _ = parse_expression(s, 0)
    return result




# Test cases
if __name__ == "__main__":
    print(basic_calculator_stack("1 + 1"))  # 2
    print(basic_calculator_stack(" 2-1 + 2 "))  # 3
    print(basic_calculator_stack("(1+(4+5+2)-3)+(6+8)"))  # 23
    print(basic_calculator_stack("2*(5+5*2)/3+(6/2*5)"))  # 17

Approach 2: Two-Pass with Postfix Notation

Section titled “Approach 2: Two-Pass with Postfix Notation”
🎯 Interview Favourite

This approach uses the Shunting Yard algorithm (Dijkstra’s) to convert infix notation to postfix (RPN), then evaluates the postfix expression.

Why two passes?

  1. First pass (Tokenize → Postfix): Converts "(1+2)*3" to "1 2 + 3 *", respecting operator precedence.
  2. Second pass (Evaluate): Processes the postfix expression using a simple stack.

This approach is more general and handles all operators with correct precedence automatically.

⏱ Time O(n) Two passes 💾 Space O(n) Postfix stack + eval stack

Step-by-step Example

Section titled “Step-by-step Example”

Input: "2*(5+5*2)/3+(6/2*5)"

Step 1: Tokenize [2, *, (, 5, +, 5, *, 2, ), /, 3, +, (, 6, /, 2, *, 5, )]

Step 2: Infix to Postfix (Shunting Yard)

Using an operator stack and output queue:

TokenOutputOp StackNotes
2[2][]Number → output
*[2][*]* onto stack
([2][*, (]( onto stack
5[2, 5][*, (]Number → output
+[2, 5][*, (, +]+ onto stack (lower precedence)
5[2, 5, 5][*, (, +]Number → output
*[2, 5, 5, +][*, (, *]Pop +, push * (higher precedence)
2[2, 5, 5, +, 2][*, (, *]Number → output
)[2, 5, 5, +, 2, *, /][*]Pop until (
/[2, 5, 5, +, 2, *, /][/]Pop * (equal precedence)
…ContinuesContinuesContinue process
Final[2, 5, 5, +, 2, *, /, 3, /, 6, 2, /, 5, *, +][]Postfix ready

Step 3: Evaluate Postfix

TokenStackAction
2[2]Push 2
5[2, 5]Push 5
5[2, 5, 5]Push 5
+[2, 10]Pop 5, 5 → 5+5=10 → push
2[2, 10, 2]Push 2
*[2, 20]Pop 2, 10 → 10*2=20 → push
/[10]Pop 20, 2 → 2/20=0 (or 20/3 depends on order)
……Continue
Final[17]Result: 17

Pseudocode

Section titled “Pseudocode”
function basicCalculatorTwoPass(s):
    tokens = tokenize(s)
    postfix = infixToPostfix(tokens)
    return evaluatePostfix(postfix)


function infixToPostfix(tokens):
    output = []
    opStack = []
    for token in tokens:
        if token is number:
            output.append(token)
        else if token == '(':
            opStack.push(token)
        else if token == ')':
            while opStack.top() != '(':
                output.append(opStack.pop())
            opStack.pop()  // discard '('
        else if token is operator:
            while opStack not empty AND opStack.top() is operator AND
                  precedence(opStack.top()) >= precedence(token):
                output.append(opStack.pop())
            opStack.push(token)
    while opStack not empty:
        output.append(opStack.pop())
    return output


function evaluatePostfix(postfix):
    stack = []
    for token in postfix:
        if token is number:
            stack.push(token)
        else:
            b = stack.pop()
            a = stack.pop()
            result = apply(token, a, b)
            stack.push(result)
    return stack[0]

Solution Code

Section titled “Solution Code”
basic_calculator_two_pass.py
def basic_calculator_two_pass(s: str) -> int:
    """
    Evaluate a mathematical expression with +, -, *, /, and parentheses.


    Approach: Two-Pass with precedence handling
    - First pass: convert infix to postfix notation (Reverse Polish Notation)
    - Second pass: evaluate postfix expression using a stack
    - Handles operator precedence (* and / before + and -)


    Time: O(n) - two passes through string
    Space: O(n) - stacks for postfix and evaluation
    """
    if not s:
        return 0


    def precedence(op: str) -> int:
        if op in "+-":
            return 1
        elif op in "*/":
            return 2
        return 0


    # Tokenize the expression
    tokens = []
    i = 0
    while i < len(s):
        if s[i].isspace():
            i += 1
        elif s[i].isdigit():
            num = 0
            while i < len(s) and s[i].isdigit():
                num = num * 10 + int(s[i])
                i += 1
            tokens.append(num)
        elif s[i] in "+-*/()":
            tokens.append(s[i])
            i += 1
        else:
            i += 1


    # Convert infix to postfix (Shunting Yard algorithm)
    output = []
    operator_stack = []


    for token in tokens:
        if isinstance(token, int):
            output.append(token)
        elif token == '(':
            operator_stack.append(token)
        elif token == ')':
            while operator_stack and operator_stack[-1] != '(':
                output.append(operator_stack.pop())
            if operator_stack:
                operator_stack.pop()  # Remove '('
        elif token in "+-*/":
            while (operator_stack and
                   operator_stack[-1] != '(' and
                   precedence(operator_stack[-1]) >= precedence(token)):
                output.append(operator_stack.pop())
            operator_stack.append(token)


    while operator_stack:
        output.append(operator_stack.pop())


    # Evaluate postfix expression
    stack = []
    for token in output:
        if isinstance(token, int):
            stack.append(token)
        else:
            b = stack.pop()
            a = stack.pop()
            if token == '+':
                stack.append(a + b)
            elif token == '-':
                stack.append(a - b)
            elif token == '*':
                stack.append(a * b)
            elif token == '/':
                # Integer division toward zero
                stack.append(int(a / b))


    return stack[0] if stack else 0




# Test cases
if __name__ == "__main__":
    print(basic_calculator_two_pass("1 + 1"))  # 2
    print(basic_calculator_two_pass(" 2-1 + 2 "))  # 3
    print(basic_calculator_two_pass("(1+(4+5+2)-3)+(6+8)"))  # 23
    print(basic_calculator_two_pass("2*(5+5*2)/3+(6/2*5)"))  # 17

Common mistakes

Section titled “Common mistakes”

Approach 3: Space-Optimized Variant

Section titled “Approach 3: Space-Optimized Variant”
✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

Section titled “Pseudocode”
function approach3():
    // Implementation approach goes here

Solution Code

Section titled “Solution Code”
basic_calculator_space_optimized.py
"""
Solution for Basic Calculator
"""


def solve():
    """Implementation for approach 3 of Basic Calculator"""
    pass


if __name__ == "__main__":
    print("Solution ready")

Interview Tips

Section titled “Interview Tips”

When to use each approach

Section titled “When to use each approach”
ScenarioApproachReason
Interview asks for simplest solutionStack with SignEasy to explain, minimal stack depth
Interview asks about scalabilityTwo-Pass PostfixGeneralizes to any precedence levels
Expression is deeply nested (1000+ levels)Stack with SignO(depth) space is better than O(n)
Expression has mixed operatorsTwo-Pass PostfixShunting Yard handles precedence correctly
You need to extend to support variables/functionsTwo-Pass PostfixEasier to add features to tokenization and evaluation

Related Problems