# Parsing A Boolean Expression
**Difficulty:** HARD
[External](https://leetcode.com/problems/parsing-a-boolean-expression)
Canonical: https://scaleengineer.com/dsa/problems/parsing-a-boolean-expression
**Patterns:** [Recursion](https://scaleengineer.com/dsa/patterns/recursion)
**Data structures:** String, Stack
**Companies:** [HiLabs](https://scaleengineer.com/companies/hilabs)
---
## Problem
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
## 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.
**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.
**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.
### Explanation
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.
### 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`.

## Iterative Evaluation using a Stack
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.
**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.
**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.
### Explanation
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.
1.  Initialize an empty stack of characters.
2.  Iterate through each character of the expression.
3.  Commas are ignored as they are just separators.
4.  If the character is not a closing parenthesis `)`, push it onto the stack. This includes operators (`!`, `&`, `|`), opening parentheses `(`, and values (`t`, `f`).
5.  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.
6.  After the entire expression has been processed, the stack will contain a single character (`t` or `f`), which is the final result.
```java
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean parseBoolExpr(String expression) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : expression.toCharArray()) {
            if (c == ',') {
                continue;
            }
            if (c != ')') {
                stack.push(c);
            } else { // c == ')'
                Set<Character> seen = new HashSet<>();
                while (stack.peek() != '(') {
                    seen.add(stack.pop());
                }
                stack.pop(); // Pop '('
                char op = stack.pop();

                char result;
                if (op == '!') {
                    result = seen.contains('f') ? 't' : 'f';
                } else if (op == '&') {
                    result = seen.contains('f') ? 'f' : 't';
                } else { // op == '|'
                    result = seen.contains('t') ? 't' : 'f';
                }
                stack.push(result);
            }
        }
        return stack.pop() == 't';
    }
}
```
### 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`.

## Recursive Descent Parser
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.
**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.
**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.
### Explanation
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.
```java
class Solution {
    int i = 0;
    String expression;

    public boolean parseBoolExpr(String s) {
        this.expression = s;
        return parse();
    }

    private boolean parse() {
        char c = expression.charAt(i++);
        if (c == 't') {
            return true;
        }
        if (c == 'f') {
            return false;
        }
        
        // c is '!', '&', or '|'
        i++; // skip '('
        
        boolean result;
        if (c == '!') {
            result = !parse();
        } else {
            boolean isAnd = (c == '&');
            result = isAnd; // Initial value: true for AND, false for OR
            while (true) {
                boolean subResult = parse();
                if (isAnd) {
                    result &= subResult;
                } else { // is OR
                    result |= subResult;
                }
                if (expression.charAt(i) == ')') {
                    break;
                }
                i++; // skip ','
            }
        }
        i++; // skip ')'
        return result;
    }
}
```
### 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`.

# Solutions
### Java

```java
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' ; } }
```

### Python

```python
class 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'
```

### CPP

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