1106. Parsing A Boolean Expression

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 ','.

Approach 01:

#include <string>
#include <vector>
#include <functional>
#include <algorithm>

class Solution {
public:
    bool parseBoolExpr(const std::string& expression) {
        return dfs(expression, 0, expression.size() - 1);
    }

private:
    bool dfs(const std::string& expression, int start, int end) {
        if (start == end)
            return expression[start] == 't';

        std::vector<bool> subExpressions;
        char operatorChar = '\0';
        int layer = 0;

        for (int i = start; i <= end; ++i) {
            char currentChar = expression[i];

            if (layer == 0 && (currentChar == '!' || currentChar == '&' || currentChar == '|')) {
                operatorChar = currentChar;
            } else if (currentChar == '(') {
                layer++;
                if (layer == 1) {
                    leftStart = i + 1;
                }
            } else if (currentChar == ')') {
                layer--;
                if (layer == 0) {
                    subExpressions.push_back(dfs(expression, leftStart, i - 1));
                }
            } else if (currentChar == ',' && layer == 1) {
                subExpressions.push_back(dfs(expression, leftStart, i - 1));
                leftStart = i + 1;
            }
        }

        if (operatorChar == '|')
            return std::any_of(subExpressions.begin(), subExpressions.end(), [](bool val) { return val; });
        if (operatorChar == '&')
            return std::all_of(subExpressions.begin(), subExpressions.end(), [](bool val) { return val; });
        if (operatorChar == '!')
            return !subExpressions[0];

        return false;
    }

    int leftStart = 0;
};

import functools
import operator

class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        def dfs(startIndex: int, endIndex: int) -> bool:
            if startIndex == endIndex:
                return True if expression[startIndex] == 't' else False

            subExpressions = []
            currentLayer = 0

            for i in range(startIndex, endIndex + 1):
                currentChar = expression[i]
                if currentLayer == 0 and currentChar in '!&|':
                    operatorChar = currentChar
                elif currentChar == '(':
                    currentLayer += 1
                    if currentLayer == 1:
                        leftStart = i + 1
                elif currentChar == ')':
                    currentLayer -= 1
                    if currentLayer == 0:
                        subExpressions.append(dfs(leftStart, i - 1))
                elif currentChar == ',' and currentLayer == 1:
                    subExpressions.append(dfs(leftStart, i - 1))
                    leftStart = i + 1

            if operatorChar == '|':
                return functools.reduce(operator.or_, subExpressions)
            if operatorChar == '&':
                return functools.reduce(operator.and_, subExpressions)
            if operatorChar == '!':
                return not subExpressions[0]

        return dfs(0, len(expression) - 1)

Time Complexity

• Recursive DFS Traversal:

  The function uses depth-first search (DFS) to traverse the expression. At each level of the expression, it processes all characters between parentheses and recursively evaluates sub-expressions. In the worst case, each character in the expression is processed once, giving a time complexity proportional to the length of the string.

• Evaluation of Subexpressions:

  Each subexpression requires constant-time checks to apply the operator (|, &, !). Thus, the time spent evaluating operators is also proportional to the number of characters in the string.

• Overall Time Complexity:

  The overall time complexity is \(O(n)\), where \(n\) is the length of the input string.

Space Complexity

• Call Stack:

  The recursive DFS calls use stack space proportional to the depth of the expression. The depth of the expression corresponds to the maximum number of nested parentheses. In the worst case, all characters are nested, which gives a recursive depth of \(O(n)\), where \(n\) is the length of the expression.

• Auxiliary Data Structures:

  A std::vector is used to store subexpression results. In the worst case, this vector can store up to \(O(n)\) boolean values. Since we are processing each character at most once, the auxiliary space usage is \(O(n)\).

• Overall Space Complexity:

  The overall space complexity is \(O(n)\), where \(n\) is the length of the input string, primarily due to the recursion depth and the auxiliary storage of subexpressions.