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

  1. Use a stack. Push operators and operands as they appear; commas are skipped.
  2. On ), pop the operands belonging to the current group (they are the t/f characters on top), then pop the operator.
  3. Apply the operator: ! negates its single operand, & is all, | is any.
  4. Push the result back as t or f so 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/any to a single operand for !: ! takes exactly one operand, so vals[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.
🎯 Drill This Card Now➔

🧩 Related Stack Problems