LeetCode 1106 - Parsing A Boolean Expression

Difficulty: 🔴 Hard
Topics: String, Stack, Recursion

Solution

Problem Understanding

The problem asks us to evaluate a boolean expression represented as a string. The expression can contain the literals 't' and 'f' for true and false, as well as three types of operators: logical NOT '!', logical AND '&', and logical OR '|'. Each operator has a specific syntax: '!(subExpr)' negates a sub-expression, '&(subExpr1,subExpr2,...)' computes the logical AND of one or more sub-expressions, and '|(subExpr1,subExpr2,...)' computes the logical OR of one or more sub-expressions. The sub-expressions themselves may be nested arbitrarily deep.

The input is a string expression of length up to 20,000 characters, which guarantees that parsing must be efficient and ideally linear. The output is a boolean value, either true or false, which corresponds to the evaluation of the expression according to standard boolean logic.

Important constraints include the guaranteed validity of the input, so we do not need to handle malformed strings. Potential edge cases include expressions with only one literal, deeply nested expressions, or operators applied to a single sub-expression. Additionally, empty sub-expression lists will not occur due to the constraints.

Approaches

A brute-force approach would attempt to parse the string recursively, splitting at commas manually, and evaluating each sub-expression. While this approach is correct, naive string splitting at commas in nested expressions can be error-prone and may require multiple scans per sub-expression, making it potentially O(n^2) in time for large nested expressions.

The optimal approach uses a stack-based parsing technique that processes the string in a single left-to-right pass. Each character is pushed onto the stack until a closing parenthesis ')' is encountered. At that point, the stack is popped until the matching opening '(' is found, gathering all sub-expressions. The corresponding operator is just before '(', so we can compute the result of the operator applied to all sub-expressions and push the resulting 't' or 'f' back onto the stack. This approach ensures that each character is processed exactly once, yielding an O(n) solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(n)	Recursively split and evaluate strings, may rescan nested sub-expressions multiple times
Optimal	O(n)	O(n)	Stack-based single pass evaluation, process each character once, efficient for deep nesting

Algorithm Walkthrough

Initialize an empty stack to hold characters from the expression as we iterate.
Iterate over each character ch in the input string:
If ch is a literal 't' or 'f', or an operator '!', '&', '|', or '(', push it onto the stack.
If ch is a closing parenthesis ')', this signals the end of a sub-expression:
Pop elements from the stack until an opening '(' is found. Gather all literals 't' or 'f' in a list.
Pop the '(' from the stack.
Pop the operator just before '(' to determine the operation.
Apply the operator to the list of sub-expression results:

'!' negates the single value.
'&' computes logical AND of all values.
'|' computes logical OR of all values.

Push the resulting 't' or 'f' back onto the stack.
At the end of the iteration, the stack will contain a single element 't' or 'f', which represents the result. Return True if it is 't', else False.

Why it works: The stack maintains the current evaluation context. By processing each closing parenthesis immediately and collapsing its sub-expression into a single boolean value, we ensure that nested expressions are evaluated before their parent expressions, respecting the order of operations and parentheses.

Python Solution

class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        stack = []
        
        for ch in expression:
            if ch == ',':
                continue
            elif ch != ')':
                stack.append(ch)
            else:
                vals = []
                while stack[-1] != '(':
                    vals.append(stack.pop())
                stack.pop()  # pop '('
                op = stack.pop()  # operator
                if op == '!':
                    result = 't' if vals[0] == 'f' else 'f'
                elif op == '&':
                    result = 't' if all(v == 't' for v in vals) else 'f'
                else:  # '|'
                    result = 't' if any(v == 't' for v in vals) else 'f'
                stack.append(result)
        
        return stack[0] == 't'

The code uses a stack to process nested expressions. We skip commas because they only separate operands. When encountering a closing parenthesis, we pop all literals until '(' is reached, determine the operator, compute the result, and push it back. At the end, the stack contains one final value, which is converted to a boolean.

Go Solution

func parseBoolExpr(expression string) bool {
    stack := []rune{}
    
    for _, ch := range expression {
        if ch == ',' {
            continue
        } else if ch != ')' {
            stack = append(stack, ch)
        } else {
            vals := []rune{}
            for stack[len(stack)-1] != '(' {
                vals = append(vals, stack[len(stack)-1])
                stack = stack[:len(stack)-1]
            }
            stack = stack[:len(stack)-1] // pop '('
            op := stack[len(stack)-1]
            stack = stack[:len(stack)-1] // pop operator
            
            var result rune
            switch op {
            case '!':
                if vals[0] == 't' {
                    result = 'f'
                } else {
                    result = 't'
                }
            case '&':
                result = 't'
                for _, v := range vals {
                    if v == 'f' {
                        result = 'f'
                        break
                    }
                }
            case '|':
                result = 'f'
                for _, v := range vals {
                    if v == 't' {
                        result = 't'
                        break
                    }
                }
            }
            stack = append(stack, result)
        }
    }
    
    return stack[0] == 't'
}

Go differs slightly in syntax: slices are used as the stack, and runes are used for character manipulation. The logic otherwise mirrors Python, ensuring a single-pass evaluation and correct handling of nested expressions.

Worked Examples

Example 1: &(|(f))

Step	Stack Content	Operation
'&'	['&']	Push operator
'('	['&','(']	Push '('
'	'	['&','(','
'('	['&','(','	','(']
'f'	['&','(','	','(','f']
')'	['&','(','	','f']
')'	['&','f']	Evaluate `&(f)` = `f`
End	['f']	Final result = false

Example 2: |(f,f,f,t)

Step	Stack Content	Operation
'	'	['
'('	['	','(']
'f'	['	','(','f']
'f'	['	','(','f','f']
'f'	['	','(','f','f','f']
't'	['	','(','f','f','f','t']
')'	['t']	Evaluate OR = `t`
End	['t']	Final result = true

Example 3: !(&(f,t))

Step	Stack Content	Operation
'!'	['!']	Push operator
'('	['!','(']	Push '('
'&'	['!','(','&']	Push operator
'('	['!','(','&','(']	Push '('
'f'	['!','(','&','(','f']	Push literal
't'	['!','(','&','(','f','t']	Push literal
')'	['!','&','f']	Evaluate `&(f,t)` = `f`
')'	['t']	Evaluate `!(f)` = `t`
End	['t']	Final result = true

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed exactly once in a single pass with a stack.
Space	O(n)	Stack may hold all characters in the worst case for deeply nested expressions.

The complexity is linear in both time and space, which is optimal given the constraints of expression length up to 20,000.