Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces.

The expression string contains only non-negative integers, +, -, *, / operators, open ( and closing parentheses ) and empty spaces. 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 of [-2^31, 2^31 - 1].

Examples

Example 1:

Input: s = "1+1"
Output: 2

Example 2:

Input: s = "6-4/2"
Output: 4

Example 3:

Input: s = "2*(5+5*2)/3+(6/2+8)"
Output: 21

Example 4:

Input: s = "(2+6*3+5-(3*14/7+2)*5)+3"
Output: -12

Constraints

  • 1 <= s.length <= 10^4
  • s consists of digits, '+', '-', '*', '/', '(', ')', and ' '.
  • s is a valid expression.

Thinking Process

  1. Recursion for Parentheses: Natural way to handle nested structures
  • Stack matches nested or LIFO structure (parentheses, monotonic scans).
  • Push on open / larger; pop when the current element resolves pending work.
  • Monotonic stack finds next greater/smaller in O(n).
Stack top push / pop LIFO — monotonic stack scans array

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Monotonic stack (this problem) O(n) O(n) Next greater/smaller element
Parentheses matching O(n) O(n) Push open, pop on close
Expression evaluation O(n) O(n) Operand + operator stacks
Stack simulation O(n) O(n) Process in LIFO order

Solution

Time Complexity: O(n)
Space Complexity: O(n) - Recursion stack depth

Use recursion to handle nested parentheses. When encountering (, recursively evaluate the expression inside. Use a stack to handle operator precedence: evaluate * and / immediately, defer + and - until the end.

class Solution:
    def parseExpr(self, s, idx):
        op = '+'
        stk = []

        while idx < len(s):
            if s[idx].isspace():
                idx += 1
                continue

            num = 0

            if s[idx] == '(':
                idx += 1
                num = self.parseExpr(s, idx)

            elif s[idx].isdigit():
                num = self.parseNum(s, idx)

            elif s[idx] == ')':
                break

            else:
                op = s[idx]
                idx += 1
                continue

            if op == '+':
                stk.append(num)
            elif op == '-':
                stk.append(-num)
            elif op == '*':
                stk[-1] = num
            elif op == '/':
                stk[-1] = stk[-1] // num

        rtn = 0
        for num in stk:
            rtn += num

        return rtn

    def parseNum(self, s, idx):
        num = 0

        while idx < len(s) and s[idx].isdigit():
            num = num * 10 + (ord(s[idx]) - ord('0'))
            idx += 1

        return num

    def calculate(self, s):
        idx = 0
        return self.parseExpr(s, idx)

Solution Explanation

Approach: Monotonic stack (this problem)

Key idea: 1. Recursion for Parentheses: Natural way to handle nested structures

How the code works:

  1. Recursion for Parentheses: Natural way to handle nested structures
    • Stack matches nested or LIFO structure (parentheses, monotonic scans).
    • Push on open / larger; pop when the current element resolves pending work.
    • Monotonic stack finds next greater/smaller in O(n).

Walkthrough — input s = "1+1", expected output 2:

  1. Initialize variables from the problem setup.
  2. Apply the main loop / recursion until the condition is met.
  3. Confirm the result matches the expected output.

| Solution | Time | Space | Notes | |———-|——|——-|——-| | Recursive | O(n) | O(n) | Natural for nested structures | | Iterative (2 stacks) | O(n) | O(n) | More explicit state management | | Simplified Iterative | O(n) | O(n) | Cleaner code, single stack |

How the Algorithms Work

Key Insight: Handling Parentheses

Parentheses change the evaluation order. We need to:

  1. Recursive approach: When seeing (, recursively evaluate the inner expression
  2. Iterative approach: Use stack to save state before ( and restore after )

Solution 1: Recursive Step-by-Step

Example: s = "2*(5+5*2)/3"

parseExpr("2*(5+5*2)/3", idx=0)
  op = '+', stk = []
  
  idx=0: '2' → num = 2
    op='+': stk.push_back(2) → stk = [2]
    op = '*'
  
  idx=1: '*' → skip (handled above)
  
  idx=2: '(' → recursive call
    parseExpr("5+5*2)/3", idx=3)
      op = '+', stk = []
      
      idx=3: '5' → num = 5
        op='+': stk.push_back(5) → stk = [5]
        op = '+'
      
      idx=4: '+' → skip
      
      idx=5: '5' → num = 5
        op='+': stk.push_back(5) → stk = [5, 5]
        op = '*'
      
      idx=6: '*' → skip
      
      idx=7: '2' → num = 2
        op='*': stk.back() *= 2 → stk = [5, 10]
        op = ')'
      
      idx=8: ')' → break, return sum([5, 10]) = 15
    
    num = 15
    op='*': stk.back() *= 15 → stk = [30]
    op = '/'
  
  idx=9: '/' → skip
  
  idx=10: '3' → num = 3
    op='/': stk.back() /= 3 → stk = [10]
  
  Return sum([10]) = 10

Solution 3: Simplified Iterative Step-by-Step

Example: s = "2*(5+5*2)/3"

Step 0: num=0, sign='+', stk=[]

Step 1: '2' → num=2
Step 2: '*' → process sign='+'
  stk.push(2) → stk=[2]
  sign='*', num=0

Step 3: '(' → push state
  stk.push(0), stk.push(1) → stk=[2, 0, 1]
  num=0, sign='+'

Step 4-5: '5' → num=5
Step 6: '+' → process sign='+'
  stk.push(5) → stk=[2, 0, 1, 5]
  sign='+', num=0

Step 7-8: '5' → num=5
Step 9: '*' → process sign='+'
  stk.push(5) → stk=[2, 0, 1, 5, 5]
  sign='*', num=0

Step 10-11: '2' → num=2
Step 12: ')' → evaluate parentheses
  Process sign='*': stk.top() *= 2 → stk=[2, 0, 1, 5, 10]
  multiplier = 1, prevSum = 0
  num = 0 + 1 * (5+10) = 15
  sign='+'

Step 13: '/' → process sign='*'
  stk.top() *= 15 → stk=[2, 30]
  sign='/', num=0

Step 14-15: '3' → num=3
End: process sign='/'
  stk.top() /= 3 → stk=[10]

Result: sum([10]) = 10

Algorithm Breakdown

Solution 1: Recursive

1. Parse Expression

class Solution:
    def calculate(self, s):
        nums = []
        ops = []

        num = 0
        op = '+'

        for i in range(len(s)):
            c = s[i]

            if c.isdigit():
                num = num * 10 + (ord(c) - ord('0'))

            if (not c.isdigit() and not c.isspace()) or i == len(s) - 1:

                if c == '(':
                    nums.append(0)
                    ops.append(op)
                    num = 0
                    op = '+'

                else:
                    # Apply current operation
                    if op == '+':
                        nums.append(num)
                    elif op == '-':
                        nums.append(-num)
                    elif op == '*':
                        top = nums.pop()
                        nums.append(top * num)
                    elif op == '/':
                        top = nums.pop()
                        nums.append(top // num)

                    if c == ')':
                        # Evaluate expression inside parentheses
                        total = 0

                        while ops and ops[-1] != '(':
                            total += nums.pop()

                        ops.pop()  # Remove '('
                        num = total

                        op = '+' if not ops else ops[-1]

                    else:
                        op = c
                        num = 0

        result = 0
        while nums:
            result += nums.pop()

        return result

2. Handle Parentheses

class Solution:
    def calculate(self, s):
        stk = []
        num = 0
        sign = '+'

        for i in range(len(s)):
            c = s[i]

            if c.isdigit():
                num = num * 10 + (ord(c) - ord('0'))

            if c == '(':
                stk.append(0)
                stk.append(1 if sign == '+' else -1)
                num = 0
                sign = '+'

            elif c == ')':
                val = num
                multiplier = stk.pop()
                prevSum = stk.pop()
                num = prevSum + multiplier * val
                sign = '+'

            elif c in "+-*/":
                if sign == '+':
                    stk.append(num)
                elif sign == '-':
                    stk.append(-num)
                elif sign == '*':
                    top = stk.pop()
                    stk.append(top * num)
                elif sign == '/':
                    top = stk.pop()
                    stk.append(top // num)

                sign = c
                num = 0

        # process last number
        if sign == '+':
            stk.append(num)
        elif sign == '-':
            stk.append(-num)
        elif sign == '*':
            top = stk.pop()
            stk.append(top * num)
        elif sign == '/':
            top = stk.pop()
            stk.append(top // num)

        result = 0
        while stk:
            result += stk.pop()

        return result

3. Handle Numbers

def parseExpr(self, s, idx):
    char op = '+'
    list[int> stk
    # Process characters...

4. Apply Operations

if s[idx] == '(':
    num = parseExpr(s, idx += 1)  # Recursive call
     else if(s[idx] == ')') :
    break  # Return from recursion

Solution 3: Simplified Iterative

1. Handle Opening Parenthesis

def if(self, isdigit(s[idx])):
    num = parseNum(s, idx)
    idx -= 1  # Adjust because parseNum advances idx

2. Handle Closing Parenthesis

switch(op) :
case '+': stk.append(num) break
case '-': stk.append(-num) break
case '': stk[-1] = num break
case '/': stk[-1] /= num break

Complexity

| Solution | Time | Space | Notes | |———-|——|——-|——-| | Recursive | O(n) | O(n) | Natural for nested structures | | Iterative (2 stacks) | O(n) | O(n) | More explicit state management | | Simplified Iterative | O(n) | O(n) | Cleaner code, single stack |

Common Mistakes

  1. Nested parentheses: "((1+2)*3)" → 9
  2. No parentheses: "1+2*3" → 7
  3. Single number: "42" → 42
  4. Negative results: "1-2" → -1
  5. Division truncation: "5/2" → 2

  6. Multiple spaces: "1 + 2" → 3

  7. Index management: Not adjusting index after parseNum or after recursive call
  8. Operator precedence: Evaluating + before *
  9. Parentheses handling: Not properly saving/restoring state
  10. Number building: Not handling multi-digit numbers
  11. Sign handling: Forgetting to push negative for -

Detailed Example Walkthrough

Example: s = "2*(5+5*2)/3"

Solution 1 (Recursive):

Main call: parseExpr("2*(5+5*2)/3", idx=0)
  op='+', stk=[]
  
  idx=0: '2' → num=2
    op='+': stk=[2]
    op='*'
  
  idx=2: '(' → recursive call
    parseExpr("5+5*2)/3", idx=3)
      op='+', stk=[]
      
      idx=3: '5' → num=5
        op='+': stk=[5]
        op='+'
      
      idx=5: '5' → num=5
        op='+': stk=[5, 5]
        op='*'
      
      idx=7: '2' → num=2
        op='*': stk=[5, 10]
        op=')'
      
      idx=8: ')' → break
      Return: 5+10 = 15
    
    num=15
    op='*': stk=[30]
    op='/'
  
  idx=10: '3' → num=3
    op='/': stk=[10]
  
  Return: 10

Pattern Recognition

This problem demonstrates the Expression Evaluation with Parentheses pattern:

  • Use recursion or stack to handle nested structures
  • Maintain operator precedence
  • Save/restore evaluation state at parentheses boundaries
  • Process operators based on precedence

Key Insight:

  • Parentheses create nested evaluation contexts
  • Recursion naturally handles nesting
  • Stack can simulate recursion iteratively

Optimization Tips

Recursive vs Iterative

  • Recursive: More intuitive, natural for nested structures
  • Iterative: Avoids recursion stack overhead, more control

Index Management

In recursive approach, be careful with index:

  • parseNum advances idx, so need idx-- after
  • Recursive call uses ++idx to skip (
  • ) naturally breaks the loop

Code Quality Notes

  1. Readability: Recursive approach is more intuitive
  2. Efficiency: Both approaches are O(n) time and space
  3. Correctness: Both handle operator precedence and parentheses correctly
  4. Maintainability: Simplified iterative approach is cleaner

This problem combines expression evaluation with nested parentheses handling. The recursive approach naturally handles nesting, while the iterative approach provides more control over the evaluation process.

Key Takeaways

  1. Recursion for Parentheses: Natural way to handle nested structures
  2. Stack for State: Save evaluation state before entering parentheses
  3. Operator Precedence: Evaluate * and / immediately, defer + and -
  4. Index Management: Careful index tracking in recursive approach
  5. Number Building: Accumulate multi-digit numbers correctly

References

Template Reference