NeetCode #371LC-227MediumStack
← Back to All Problems#371 · #227 · Basic Calculator II(基本计算器 II)
📌 Problem Statement & Constraints
Given a string
s representing an expression with non-negative integers and the operators +, -, *, /, evaluate it. Division truncates toward zero and there is no operator precedence to parse for parentheses. Constraints: 1 <= s.length <= 3 * 10^5; the expression is always valid.💡 Core Algorithmic Approaches
- Use a stack to handle precedence:
+and-push the signed number, while*and/combine immediately with the stack top. - Accumulate multi-digit numbers as they are scanned.
- Trigger the operator handling when a non-digit (other than a space) is seen, or at the last character -- otherwise the final number would never be applied.
- The answer is the sum of the stack.
💻 Benchmark Python3 Implementation
class Solution:
def calculate(self, s: str) -> int:
st = []
num = 0
op = "+" # pending operator
for i, ch in enumerate(s):
if ch.isdigit():
num = num * 10 + int(ch) # multi-digit numbers
if (not ch.isdigit() and ch != " ") or i == len(s) - 1:
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
num = 0
op = ch # remember the operator for the next number
return sum(st)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass with O(1) work per character.
💾 Space Complexity
O(n) for the stack (one entry per additive term).
⚠️ Interview Pitfalls & Follow-ups
- Forgetting the
i == len(s) - 1condition: the last number would never be applied. - Using
//for division: Python floors toward negative infinity;int(a / b)truncates toward zero. - Trying to evaluate strictly left to right: precedence requires either a stack or a two-pass approach.
- Not skipping spaces: they appear throughout the expression.
- Overwriting
opwith a space: the operator update must only happen on actual operators, which the condition handles.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.