⚡Flashcard Drill➔
NeetCode #365LC-772HardStackNC Algo100
← Back to All Problems

#365 · #772 · Basic Calculator III(基本计算器 III)

📌 Problem Statement & Constraints

Implement a basic calculator to evaluate a simple expression string containing non-negative integers, +, -, *, /, ( and ). Division truncates toward zero. Constraints: 1 <= s.length <= 10^4; the expression is always valid.

💡 Core Algorithmic Approaches

  1. Combine the techniques from Basic Calculator I (parentheses) and II (operator precedence).
  2. A recursive helper evaluates the expression from a given index, stopping at ) or the end, and returns both the value and the stopping index.
  3. Within a level, a stack handles precedence: +/- push the signed number, while *// combine with the stack top immediately.
  4. After a recursive call for (, the sub-value is stored in num and the enclosing operator applies on the next operator character -- so the index must skip past the ) without treating ( as an operator.

💻 Benchmark Python3 Implementation

class Solution:
    def calculate(self, s: str) -> int:
        def parse(i: int):
            """Evaluate from index i, stopping at ')' or the end.
            Returns (value, index)."""
            st = []
            num = 0
            op = "+"

            def apply() -> None:
                if op == "+":
                    st.append(num)
                elif op == "-":
                    st.append(-num)
                elif op == "*":
                    st.append(st.pop() * num)
                else:
                    st.append(int(st.pop() / num))   # truncate toward zero

            while i < len(s):
                ch = s[i]
                if ch == " ":
                    i += 1
                    continue
                if ch.isdigit():
                    num = num * 10 + int(ch)
                elif ch == "(":
                    num, i = parse(i + 1)  # i now points at ')'
                    i += 1                 # skip the ')'
                    continue               # num holds the sub-value; op unchanged
                elif ch == ")":
                    apply()
                    return sum(st), i
                else:                      # an operator
                    apply()
                    num = 0
                    op = ch
                i += 1
            apply()
            return sum(st), i

        return parse(0)[0]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each character is visited once.
💾 Space Complexity
O(d) for the recursion depth plus the stacks, where d is the parenthesis nesting depth.

⚠️ Interview Pitfalls & Follow-ups

  • Applying the operator immediately after a recursive call: the sub-value must be held in num until the next operator arrives; applying straight away double-counts it.
  • Treating ( as an operator: after the recursive call, the index must skip past ) and continue, leaving op untouched.
  • Using // for division: Python floors toward negative infinity; int(a / b) truncates toward zero, which is what the problem expects.
  • Not handling spaces: they can appear anywhere and must be skipped.
  • Trying a single-pass shunting-yard implementation: correct but far more code; the recursive-descent form is easier to verify.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Stack Problems