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

String Stack

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.
'&(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

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.

This approach avoids recursion by using a stack to manage the nested structure of the expression. It processes the expression iteratively. When a closing parenthesis ) is encountered, it signifies the end of a sub-expression, which is then evaluated by popping its components from the stack.

Algorithm

Initialize an empty stack.
For each character c in the expression:
- If c is a comma, skip it.
- If c is not ), push it onto the stack.
- If c is ):
  - Initialize a temporary set seen_values.
  - While the top of the stack is not (:
    - Pop a character and add it to seen_values.
  - Pop the (.
  - Pop the operator op from the stack.
  - Calculate the result_char based on op and seen_values.
  - Push result_char onto the stack.
The final result is the boolean value of the single character left on the stack.

Walkthrough

We iterate through the expression string from left to right. We use a stack to keep track of the operators and operands of the expressions we are currently inside.

Initialize an empty stack of characters.
Iterate through each character of the expression.
Commas are ignored as they are just separators.
If the character is not a closing parenthesis ), push it onto the stack. This includes operators (!, &, |), opening parentheses (, and values (t, f).
If the character is a closing parenthesis ), we have found a complete sub-expression to evaluate.
- Pop characters from the stack until an opening parenthesis ( is found. These characters will be the t and f results of the inner expressions. Collect them (e.g., in a Set for efficient lookup).
- Pop the opening parenthesis (.
- The character now at the top of the stack is the operator for this sub-expression. Pop it.
- Evaluate the operation based on the operator and the collected t/f values. For &, check for any f. For |, check for any t. For !, negate the single value.
- Push the character representing the result (t or f) back onto the stack.
After the entire expression has been processed, the stack will contain a single character (t or f), which is the final result.

1import java.util.ArrayDeque;2import java.util.Deque;3import java.util.HashSet;4import java.util.Set;5 6class Solution {7    public boolean parseBoolExpr(String expression) {8        Deque<Character> stack = new ArrayDeque<>();9        for (char c : expression.toCharArray()) {10            if (c == ',') {11                continue;12            }13            if (c != ')') {14                stack.push(c);15            } else { // c == ')'16                Set<Character> seen = new HashSet<>();17                while (stack.peek() != '(') {18                    seen.add(stack.pop());19                }20                stack.pop(); // Pop '('21                char op = stack.pop();22 23                char result;24                if (op == '!') {25                    result = seen.contains('f') ? 't' : 'f';26                } else if (op == '&') {27                    result = seen.contains('f') ? 'f' : 't';28                } else { // op == '|'29                    result = seen.contains('t') ? 't' : 'f';30                }31                stack.push(result);32            }33        }34        return stack.pop() == 't';35    }36}

Complexity

Time

`O(N)`, where N is the length of the expression. Each character is pushed onto and popped from the stack at most once.

Space

`O(N)`. In the worst case of a deeply nested expression like `&(&(...(t)...))`, the stack depth can be proportional to N.

Trade-offs

Pros

Efficient with linear time and space complexity.
Avoids recursion, thus not subject to stack depth limitations.
Robust and standard technique for parsing nested structures.

Cons

Can be slightly less intuitive to write compared to a direct recursive solution.

This is a classic and efficient parsing technique that uses recursion to navigate the expression's structure. Instead of creating substrings, it uses a global pointer to traverse the input string, avoiding the overhead of string manipulation and achieving linear time complexity.

Algorithm

Use a global index i, initialized to 0.
Define a recursive function parse():
- Read character c at index i and advance i.
- If c is 't' or 'f', return true or false respectively.
- If c is an operator op:
  - Advance i to skip (.
  - If op is !, recursively call parse() once, negate the result, advance i past ), and return.
  - If op is & or |, initialize a result variable (true for &, false for |).
  - Start a loop:
    - Recursively call parse() to get sub_result.
    - Update result by combining it with sub_result using the current operator.
    - Check the character at i. If it's ), break the loop. If it's ,, advance i and continue.
  - Advance i past ).
  - Return result.

Walkthrough

A single recursive function, say parse(), is the core of this parser. It maintains a global index i that points to the current character being processed in the expression string.

The parse() function inspects expression[i]:
- If it's 't' or 'f', this is a base case. It returns the corresponding boolean value and increments i to move to the next character.
- If it's an operator (!, &, |), it's a recursive case. The function notes the operator, advances i past the operator and the opening (, and then enters a loop. Inside the loop, it recursively calls parse() to evaluate each sub-expression.
The loop continues until a closing parenthesis ) is encountered. The character after each sub-expression (',' or ')') dictates whether to continue the loop or finish.
After all sub-expressions for an operator are evaluated, the results are combined, and the final value is returned.

This approach can be further optimized with short-circuit evaluation. For example, in an & expression, if any sub-expression evaluates to false, the entire expression is false, and the remaining sub-expressions don't need to be evaluated. This would involve adding logic to skip parts of the string, improving average-case performance.

1class Solution {2    int i = 0;3    String expression;4 5    public boolean parseBoolExpr(String s) {6        this.expression = s;7        return parse();8    }9 10    private boolean parse() {11        char c = expression.charAt(i++);12        if (c == 't') {13            return true;14        }15        if (c == 'f') {16            return false;17        }18        19        // c is '!', '&', or '|'20        i++; // skip '('21        22        boolean result;23        if (c == '!') {24            result = !parse();25        } else {26            boolean isAnd = (c == '&');27            result = isAnd; // Initial value: true for AND, false for OR28            while (true) {29                boolean subResult = parse();30                if (isAnd) {31                    result &= subResult;32                } else { // is OR33                    result |= subResult;34                }35                if (expression.charAt(i) == ')') {36                    break;37                }38                i++; // skip ','39            }40        }41        i++; // skip ')'42        return result;43    }44}

Complexity

Time

`O(N)`, as each character of the expression is processed a constant number of times.

Space

`O(N)` for the recursion stack in the worst case of a deeply nested expression.

Trade-offs

Pros

Elegant and directly models the expression's grammar.
Very efficient with O(N) time and space complexity.
Avoids overhead of explicit data structures like a stack for parsing logic.
Can be easily extended with short-circuiting for better average performance.

Cons

Can lead to stack overflow on extremely deep expressions, though not an issue with the given constraints.

Solutions

Solution

1class 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' ; } }

1class Solution : def parseBoolExpr ( self , expression : str ) -> bool : stk = [] for c in expression : if c in 'tf!&|' : stk . append ( c ) elif c == ')' : t = f = 0 while stk [ - 1 ] in 'tf' : t += stk [ - 1 ] == 't' f += stk [ - 1 ] == 'f' stk . pop () match stk . pop (): case '!' : c = 't' if f else 'f' case '&' : c = 'f' if f else 't' case '|' : c = 't' if t else 'f' stk . append ( c ) return stk [ 0 ] == 't'

1class Solution { public: bool parseBoolExpr ( string expression ) { stack < char > stk ; for ( char c : expression ) { if ( c != '(' && c != ')' && c != ',' ) stk . push ( c ); else if ( c == ')' ) { int t = 0 , f = 0 ; while ( stk . top () == 't' || stk . top () == 'f' ) { t += stk . top () == 't' ; f += stk . top () == 'f' ; stk . pop (); } char op = stk . top (); stk . pop (); if ( op == '!' ) c = f ? 't' : 'f' ; if ( op == '&' ) c = f ? 'f' : 't' ; if ( op == '|' ) c = t ? 't' : 'f' ; stk . push ( c ); } } return stk . top () == '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 problem

Solution

1class 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' ; } }

1class Solution : def parseBoolExpr ( self , expression : str ) -> bool : stk = [] for c in expression : if c in 'tf!&|' : stk . append ( c ) elif c == ')' : t = f = 0 while stk [ - 1 ] in 'tf' : t += stk [ - 1 ] == 't' f += stk [ - 1 ] == 'f' stk . pop () match stk . pop (): case '!' : c = 't' if f else 'f' case '&' : c = 'f' if f else 't' case '|' : c = 't' if t else 'f' stk . append ( c ) return stk [ 0 ] == 't'

1class Solution { public: bool parseBoolExpr ( string expression ) { stack < char > stk ; for ( char c : expression ) { if ( c != '(' && c != ')' && c != ',' ) stk . push ( c ); else if ( c == ')' ) { int t = 0 , f = 0 ; while ( stk . top () == 't' || stk . top () == 'f' ) { t += stk . top () == 't' ; f += stk . top () == 'f' ; stk . pop (); } char op = stk . top (); stk . pop (); if ( op == '!' ) c = f ? 't' : 'f' ; if ( op == '&' ) c = f ? 'f' : 't' ; if ( op == '|' ) c = t ? 't' : 'f' ; stk . push ( c ); } } return stk . top () == 't' ; } };

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.