NeetCode #380LC-1106HardStack
← Back to All Problems#380 · #1106 · Parsing A Boolean Expression(解析布尔表达式)
📌 Problem Statement & Constraints
A boolean expression is a string containing
t (true), f (false), !(expr), &(expr,...) or |(expr,...). Evaluate it and return the result. Constraints: 1 <= expression.length <= 2 * 10^4; the expression is always valid.💡 Core Algorithmic Approaches
- Use a stack. Push operators and operands as they appear; commas are skipped.
- On
), pop the operands belonging to the current group (they are thet/fcharacters on top), then pop the operator. - Apply the operator:
!negates its single operand,&isall,|isany. - Push the result back as
torfso it can participate in the enclosing group.
💻 Benchmark Python3 Implementation
class Solution:
def parseBoolExpr(self, expression: str) -> bool:
st = []
for ch in expression:
if ch == ",":
continue # separators carry no information
if ch in "tf!&|":
st.append(ch) # operand or operator
else: # ch == ')'
vals = []
while st[-1] in "tf": # collect this group's operands
vals.append(st.pop() == "t")
op = st.pop() # the operator for this group
if op == "!":
st.append("t" if not vals[0] else "f")
elif op == "&":
st.append("t" if all(vals) else "f")
else: # '|'
st.append("t" if any(vals) else "f")
return st[-1] == "t"⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each character is pushed or popped once, and the all/any scans are bounded by the number of operands in the group.
💾 Space Complexity
O(n) for the stack.
⚠️ Interview Pitfalls & Follow-ups
- Not skipping commas: they would be pushed as if they were operands and break the grouping.
- Popping the operator before the operands: the operands are on top, so they must be collected first.
- Applying
all/anyto a single operand for!:!takes exactly one operand, sovals[0]is used directly. - Returning the stack contents: the answer is whether the single remaining entry is
t.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.