Parsing A Boolean Expression

HARD

Description

A boolean expression is an expression that evaluates to either true or false. It can be in one of the following shapes:

't' that evaluates to true.
'f' that evaluates to false.
'!(subExpr)' that evaluates to the logical NOT of the inner expression subExpr.
'&(subExpr₁, subExpr₂, ..., subExpr_n)' that evaluates to the logical AND of the inner expressions subExpr₁, subExpr₂, ..., subExpr_n where n >= 1.
'|(subExpr₁, subExpr₂, ..., subExpr_n)' that evaluates to the logical OR of the inner expressions subExpr₁, subExpr₂, ..., subExpr_n where n >= 1.

Given a string expression that represents a boolean expression, return the evaluation of that expression.

It is guaranteed that the given expression is valid and follows the given rules.

Example 1:

Input: expression = "&(|(f))"
Output: false
Explanation: 
First, evaluate |(f) --> f. The expression is now "&(f)".
Then, evaluate &(f) --> f. The expression is now "f".
Finally, return false.

Example 2:

Input: expression = "|(f,f,f,t)"
Output: true
Explanation: The evaluation of (false OR false OR false OR true) is true.

Example 3:

Input: expression = "!(&(f,t))"
Output: true
Explanation: 
First, evaluate &(f,t) --> (false AND true) --> false --> f. The expression is now "!(f)".
Then, evaluate !(f) --> NOT false --> true. We return true.

Constraints:

1 <= expression.length <= 2 * 10⁴
expression[i] is one following characters: '(', ')', '&', '|', '!', 't', 'f', and ','.

Approaches

Checkout 3 different approaches to solve Parsing A Boolean Expression. Click on different approaches to view the approach and algorithm in detail.

Naive Recursion with String Manipulation

This approach directly translates the recursive definition of the boolean expression into a recursive function. It operates by creating substrings for each sub-expression and calling itself on them. While conceptually straightforward, this method is highly inefficient due to the overhead of string manipulation.

Algorithm

Define a function parse(expression_string).
If expression_string is "t", return true.
If expression_string is "f", return false.
Identify the operator op and extract the inner content string content.
If op is !, return !parse(content).
If op is & or |:
- Split content into a list of sub_expression_strings based on top-level commas.
- Create a list of results by calling parse on each sub_expression_string.
- If op is &, return the logical AND of all results.
- If op is |, return the logical OR of all results.

The core idea is a function parse(string s) that evaluates the expression represented by s.

The base cases are when s is simply "t" or "f".
For a compound expression like op(sub1, sub2, ...):
1. The function first identifies the operator (!, &, or |) at the beginning of the string.
2. It then extracts the inner content by taking a substring that excludes the operator and the outer parentheses.
3. The most complex part is splitting this inner content into individual sub-expressions. This requires scanning the string and splitting by commas that are at the top level (i.e., not enclosed within nested parentheses). This can be done by keeping a balance counter for parentheses.
4. The function then calls itself recursively on each of these sub-expression strings.
5. Finally, it combines the boolean results from the recursive calls using the identified operator.

Complexity Analysis

Time Complexity: `O(N^2)`, where N is the length of the expression. The repeated creation of substrings and scanning to split the string at each level of recursion leads to quadratic complexity. For example, in an expression like `&(&(...(t)...))`, each recursive call processes a string only slightly smaller than the parent, leading to `O(N^2)` work.Space Complexity: `O(N^2)` in the worst case. At each level of recursion, new strings are created for sub-expressions. With a recursion depth of `O(N)`, the total space for these strings can become quadratic.

Pros and Cons

Pros:

Directly models the problem's recursive definition.

Cons:

Highly inefficient due to repeated string scanning and substring creation.
High memory usage.
Implementation of sub-expression splitting is complex and error-prone.

Code Solutions

Checking out 3 solutions in different languages for Parsing A Boolean Expression. Click on different languages to view the code.

class Solution { public boolean parseBoolExpr ( String expression ) { Deque < Character > stk = new ArrayDeque <>(); for ( char c : expression . toCharArray ()) { if ( c != '(' && c != ')' && c != ',' ) { stk . push ( c ); } else if ( c == ')' ) { int t = 0 , f = 0 ; while ( stk . peek () == 't' || stk . peek () == 'f' ) { t += stk . peek () == 't' ? 1 : 0 ; f += stk . peek () == 'f' ? 1 : 0 ; stk . pop (); } char op = stk . pop (); c = 'f' ; if (( op == '!' && f > 0 ) || ( op == '&' && f == 0 ) || ( op == '|' && t > 0 )) { c = 't' ; } stk . push ( c ); } } return stk . peek () == 't' ; } }

Video Solution

Watch the video walkthrough for Parsing A Boolean Expression

Patterns:

Recursion

Data Structures:

StringStack

Companies:

HiLabs |