⚡Flashcard Drill➔
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

  1. Use a stack to handle precedence: + and - push the signed number, while * and / combine immediately with the stack top.
  2. Accumulate multi-digit numbers as they are scanned.
  3. 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.
  4. 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) - 1 condition: 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 op with 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.
🎯 Drill This Card Now➔

🧩 Related Stack Problems