Parsing a Boolean Expression — Solution

Problem

A boolean expression is a string that evaluates to either true or false. It can be a literal t or f, a logical NOT !(expr) applied to one inner expression, or a multi-argument AND &(e1,e2,...) or OR |(e1,e2,...) applied to any number of inner expressions. Operators can be nested arbitrarily deep.

• Input: expression = "|(f,&(t,f))"
• Output: false
• Explanation: &(t,f) is false, so |(f,false) is also false.

Counter-example: "&(t,t,t)" → true, but "&(t,t,f)" → false — every single argument must be true for & to succeed.

Intuition

The grammar is recursive: each operator takes sub-expressions as arguments, and those sub-expressions may themselves be compound. Recursive descent parsing matches this structure directly — inspect the current character to identify the operator, recurse to resolve each argument, then apply the operator to the collected results. Threading a single mutable index pointer through every recursive call lets us advance through the string exactly once without copying any substrings.

Solution — Recursive Descent

Inspect the character at the current index to decide what to do: return a literal immediately, or advance past the operator and its opening (, collect recursively parsed arguments while skipping commas, advance past the closing ), and apply the operator.

1. If the current character is t or f, advance the index by 1 and return the corresponding boolean.
2. Otherwise, read the operator character and advance by 2 to skip it and the opening (.
3. If the operator is !, parse exactly one inner expression, advance past ), and return its negation.
4. For & or |, loop until the current character is ): skip commas and recursively parse each argument, collecting results.
5. Advance past the closing ), then return all(results) for & or any(results) for |.

1def parseBoolExpr(self, expression: str) -> bool:
2    self.index = 0
3
4    def parse() -> bool:
5        char = expression[self.index]
6
7        if char == 't':
8            self.index += 1
9            return True
10        if char == 'f':
11            self.index += 1
12            return False
13
14        operator = char
15        self.index += 2  # skip the operator character and its opening '('
16
17        if operator == '!':
18            result = not parse()
19            self.index += 1  # skip closing ')'
20            return result
21
22        values = []
23        while expression[self.index] != ')':
24            if expression[self.index] == ',':
25                self.index += 1  # skip the comma separator between arguments
26            else:
27                values.append(parse())
28        self.index += 1  # skip closing ')'
29
30        return all(values) if operator == '&' else any(values)
31
32    return parse()

Time: O(n) — the index advances monotonically through the string, so each character is visited exactly once across all recursive calls.

Space: O(d) where d is the maximum nesting depth of the expression; in the worst case (a fully linear chain of operators) this is O(n).

Complexity Summary

Common Mistakes

• Not skipping comma separators — inside the argument-collection loop, commas appear between arguments and must be explicitly skipped; trying to recurse on a , character will mis-identify it as an operator.
• Applying the &/| loop to ! — ! takes exactly one argument; using the multi-argument loop for it would consume the closing ) as if it were another argument and corrupt the index for the parent call.
• Off-by-one when entering an operator — advancing by only 1 (skipping just the operator character) leaves the index pointing at (, which the next parse() call will misread as an operator; you must skip 2 characters to land on the first argument.
• Forgetting to advance past the closing ) — without the index += 1 after the loop, the parent call reads the ) as the start of the next sub-expression, producing a wrong result or an infinite loop.
• Forgetting to reset the index field between test cases — the instance variable index carries over across calls; if not reset to 0 at the start of parseBoolExpr, the second call begins mid-string.

Related Problems

• Decode String — same recursive nested-bracket structure: operator before the bracket, arguments inside, context restored after
• Evaluate Reverse Polish Notation — expression evaluation using an explicit stack instead of recursion
• Valid Parentheses — foundational bracket-matching logic that all nested expression parsers build on
• Generate Parentheses — constructing well-formed nested bracket strings by tracking open/close balance
• Longest Valid Parentheses — finding balanced regions with a stack that tracks unmatched bracket positions