1106. Parsing A Boolean Expression - Detailed Explanation

Problem Statement

You are given a string representing a Boolean expression. The expression can contain the following elements:

Literals:
- 't' for true
- 'f' for false
Operators:
- NOT represented by '!'
- AND represented by '&'
- OR represented by '|'
Parentheses '(' and ')' enclose the arguments of each operator.
Comma ',' separates multiple arguments.

The grammar is defined such that:

A literal is a valid expression.
For an operator, the expression is of the form:
- NOT: "!(expression)"
- AND: "&(expression1,expression2,...)"
- OR: "|(expression1,expression2,...)"

The goal is to evaluate the Boolean expression and return its Boolean result.

Example Inputs and Explanations

Input: !(f)
Output: true
Explanation: The NOT operator inverts f (false) to produce t (true).
Input: |(f,t)
Output: true
Explanation: The OR operator returns true if at least one of the operands is true. Here, one operand is t.
Input: &(t,f)
Output: false
Explanation: The AND operator returns true only if all operands are true. Since one operand is f, the result is false.

Constraints

The length of the expression is at least 1 and can be as large as 20,000 characters.
The expression is guaranteed to be a valid Boolean expression following the rules above.
Valid characters include: 't', 'f', '!', '&', '|', '(', ')', and ','.

Hints

Hint 1: Consider recursively breaking down the expression. Think of the expression as a tree where each operator applies to one or more subexpressions.
Hint 2: Use a stack (or recursion) to manage nested parentheses. As you scan the expression, you can process the innermost expression first and combine results upward.
Hint 3: Try to simulate the evaluation by handling each operator:
- For !, return the negation of the subresult.
- For &, check if every subexpression evaluates to true.
- For |, check if at least one subexpression evaluates to true.

Approach 1: Recursive Depth-First Search (Optimal)

Idea

The recursive solution works by “parsing” the expression from left to right. When an operator is encountered, the algorithm:

Skips the operator and its opening parenthesis.
Recursively evaluates each argument (which may be a nested expression).
Applies the operator (NOT, AND, OR) on the results.
Continues until the entire string is processed.

Walkthrough with a Visual Example

Consider the expression:

|(f, &(t, !(f)))

The outer operator is OR (|).
It has two arguments:
- The first is a literal f.
- The second is an AND expression: &(t, !(f)).
For the AND expression:
- The first argument is t.
- The second argument is a NOT expression: !(f) which evaluates to t.
- The AND of t and t yields t.
Finally, the OR of f and t is t.

Python Code

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

Time Complexity:
The recursive DFS solution processes each character in the expression exactly once. Hence, the time complexity is O(n), where n is the length of the expression.
Space Complexity:
The space used is mainly due to the recursion stack, which in the worst case can be O(n) if the expression is deeply nested.

Approach 2: Brute Force Using Iterative Replacement

Idea

A brute force method involves repeatedly finding the innermost sub-expression (one that does not contain any further nested parentheses), evaluating it, and then replacing that sub-expression in the string with its Boolean result (t or f). Continue this process until the entire expression reduces to a single literal.

Step-by-Step Walkthrough

Find the Innermost Expression:
Scan the string to locate a pair of matching parentheses that does not contain any other parentheses inside.
Evaluate the Sub-Expression:
Based on the operator preceding the parentheses, evaluate the sub-expression.
- For !, simply invert the value.
- For &, check if all values are true.
- For |, check if at least one value is true.
Replace the Expression:
Replace the entire segment (operator, parentheses, and contents) with the resulting literal.
Repeat:
Continue this process until no parentheses remain.

Drawbacks

Inefficiency:
This method may require multiple scans of the string, leading to a worse-case time complexity of O(n²) for large expressions.
String Manipulation Overhead:
Repeatedly modifying the string can be expensive.

Pseudocode Outline

while expression contains '(':
    for each character in expression:
         if found an innermost parenthesis:
              evaluate it based on the operator before it
              replace that substring with 't' or 'f'
return the final literal as the result

Note: Due to its inefficiency, this approach is not recommended for production-level interview problems, but it can help in understanding the parsing process.

Common Mistakes and Edge Cases

Common Mistakes

Mishandling Nested Expressions:
Not correctly matching parentheses when expressions are deeply nested.
Incorrect Index Management:
Losing track of the current position while using recursion or a stack can lead to out-of-bound errors.
Operator Misinterpretation:
Mixing up the behavior of !, &, and | can result in wrong answers.

Edge Cases

Single Literal Input:
The expression is just "t" or "f".
Deep Nesting:
Expressions that are nested many layers deep (e.g., multiple levels of negations).
Multiple Arguments:
Ensure that the solution correctly handles operators with more than two operands.

Variations

Additional Operators:
Problems might introduce other operators (e.g., XOR) or modify the format of the Boolean expressions.
Arithmetic Expressions:
Similar techniques are used in parsing arithmetic expressions (Basic Calculator problems).

Evaluate Reverse Polish Notation:
Use a stack to evaluate expressions written in postfix notation.
Basic Calculator I / II / III:
These problems involve parsing and evaluating mathematical expressions.
Construct Binary Expression Tree:
Convert an infix expression into a binary tree and then evaluate it.
Infix to Postfix Conversion:
Practice converting infix expressions to postfix notation before evaluation.