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
- Combine the techniques from Basic Calculator I (parentheses) and II (operator precedence).
- A recursive helper evaluates the expression from a given index, stopping at
)or the end, and returns both the value and the stopping index. - Within a level, a stack handles precedence:
+/-push the signed number, while*//combine with the stack top immediately. - After a recursive call for
(, the sub-value is stored innumand 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
numuntil 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, leavingopuntouched. - 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.