Scale Engineer

Parsing A Boolean Expression

Hard
#1047Time: `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: `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.1 company
Patterns
Recursion
Data structures
StringStack
Companies
HiLabs

Prompt

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.
  • '&(subExpr1, subExpr2, ..., subExprn)' that evaluates to the logical AND of the inner expressions subExpr1, subExpr2, ..., subExprn where n >= 1.
  • '|(subExpr1, subExpr2, ..., subExprn)' that evaluates to the logical OR of the inner expressions subExpr1, subExpr2, ..., subExprn 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 * 104
  • expression[i] is one following characters: '(', ')', '&', '|', '!', 't', 'f', and ','.

Approaches

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

`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

`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.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem