1106. Parsing A Boolean Expression - Leetcode Solution

Code Implementation

class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        def eval_expr(expr):
            if expr == 't':
                return True
            if expr == 'f':
                return False
            op = expr[0]
            stack = []
            i = 2  # skip operator and '('
            while i < len(expr) - 1:
                if expr[i] == ',':
                    i += 1
                    continue
                if expr[i] in 'tf':
                    stack.append(expr[i])
                    i += 1
                elif expr[i] in '&|!':
                    # Find the matching parenthesis
                    cnt = 0
                    j = i
                    while j < len(expr):
                        if expr[j] == '(':
                            cnt += 1
                        elif expr[j] == ')':
                            cnt -= 1
                        if cnt == 0:
                            break
                        j += 1
                    stack.append(expr[i:j+1])
                    i = j + 1
            if op == '!':
                return not eval_expr(stack[0])
            elif op == '&':
                return all(eval_expr(s) if s not in 'tf' else (s == 't') for s in stack)
            else:  # '|'
                return any(eval_expr(s) if s not in 'tf' else (s == 't') for s in stack)
        return eval_expr(expression)

class Solution {
public:
    bool parseBoolExpr(string expression) {
        return evalExpr(expression);
    }
    bool evalExpr(const string& expr) {
        if (expr == "t") return true;
        if (expr == "f") return false;
        char op = expr[0];
        vector<string> stack;
        int i = 2; // skip op and '('
        while (i < expr.size() - 1) {
            if (expr[i] == ',') {
                i++;
                continue;
            }
            if (expr[i] == 't' || expr[i] == 'f') {
                stack.push_back(string(1, expr[i]));
                i++;
            } else if (expr[i] == '&' || expr[i] == '|' || expr[i] == '!') {
                int cnt = 0, j = i;
                while (j < expr.size()) {
                    if (expr[j] == '(') cnt++;
                    if (expr[j] == ')') cnt--;
                    if (cnt == 0) break;
                    j++;
                }
                stack.push_back(expr.substr(i, j - i + 1));
                i = j + 1;
            }
        }
        if (op == '!') {
            return !evalExpr(stack[0]);
        } else if (op == '&') {
            for (auto& s : stack) {
                bool v = (s == "t") ? true : (s == "f" ? false : evalExpr(s));
                if (!v) return false;
            }
            return true;
        } else { // '|'
            for (auto& s : stack) {
                bool v = (s == "t") ? true : (s == "f" ? false : evalExpr(s));
                if (v) return true;
            }
            return false;
        }
    }
};

class Solution {
    public boolean parseBoolExpr(String expression) {
        return evalExpr(expression);
    }
    private boolean evalExpr(String expr) {
        if (expr.equals("t")) return true;
        if (expr.equals("f")) return false;
        char op = expr.charAt(0);
        List<String> stack = new ArrayList<>();
        int i = 2; // skip op and '('
        while (i < expr.length() - 1) {
            if (expr.charAt(i) == ',') {
                i++;
                continue;
            }
            if (expr.charAt(i) == 't' || expr.charAt(i) == 'f') {
                stack.add(String.valueOf(expr.charAt(i)));
                i++;
            } else if (expr.charAt(i) == '&' || expr.charAt(i) == '|' || expr.charAt(i) == '!') {
                int cnt = 0, j = i;
                while (j < expr.length()) {
                    if (expr.charAt(j) == '(') cnt++;
                    if (expr.charAt(j) == ')') cnt--;
                    if (cnt == 0) break;
                    j++;
                }
                stack.add(expr.substring(i, j + 1));
                i = j + 1;
            }
        }
        if (op == '!') {
            return !evalExpr(stack.get(0));
        } else if (op == '&') {
            for (String s : stack) {
                boolean v = s.equals("t") ? true : (s.equals("f") ? false : evalExpr(s));
                if (!v) return false;
            }
            return true;
        } else { // '|'
            for (String s : stack) {
                boolean v = s.equals("t") ? true : (s.equals("f") ? false : evalExpr(s));
                if (v) return true;
            }
            return false;
        }
    }
}

var parseBoolExpr = function(expression) {
    function evalExpr(expr) {
        if (expr === 't') return true;
        if (expr === 'f') return false;
        let op = expr[0];
        let stack = [];
        let i = 2; // skip op and '('
        while (i < expr.length - 1) {
            if (expr[i] === ',') {
                i++;
                continue;
            }
            if (expr[i] === 't' || expr[i] === 'f') {
                stack.push(expr[i]);
                i++;
            } else if (expr[i] === '&' || expr[i] === '|' || expr[i] === '!') {
                let cnt = 0, j = i;
                while (j < expr.length) {
                    if (expr[j] === '(') cnt++;
                    if (expr[j] === ')') cnt--;
                    if (cnt === 0) break;
                    j++;
                }
                stack.push(expr.slice(i, j + 1));
                i = j + 1;
            }
        }
        if (op === '!') {
            return !evalExpr(stack[0]);
        } else if (op === '&') {
            return stack.every(s => s === 't' ? true : (s === 'f' ? false : evalExpr(s)));
        } else { // '|'
            return stack.some(s => s === 't' ? true : (s === 'f' ? false : evalExpr(s)));
        }
    }
    return evalExpr(expression);
};

Problem Description

Given a string expression representing a boolean expression, return the result of evaluating it. The expression is guaranteed to be valid and consists of:

Operands: 't' (true), 'f' (false)
Operators: '!' (NOT), '&' (AND), '|' (OR)
Parentheses '(' and ')' and commas ',' to separate arguments

The structure matches standard boolean logic, but with single-letter operators and operands. The operators may have nested expressions as arguments. The goal is to compute the boolean value (True/False) of the entire expression.

Thought Process

To solve this problem, I first recognized that the expression is a nested structure, much like arithmetic expressions with parentheses. The main challenge is correctly handling operator precedence and nested sub-expressions.

A brute-force approach would be to repeatedly scan the string for innermost parentheses, evaluate them, and replace them with their results. However, this can be inefficient and error-prone due to the need to manipulate strings and track indices.

Instead, a more systematic approach is to use recursion: whenever we encounter a sub-expression (e.g., &(t,f)), we recursively evaluate its arguments, then apply the operator. This way, we naturally handle nesting, and the code becomes easier to reason about.

The analogy is similar to evaluating a tree: each node (operator) applies to its children (arguments), which may themselves be subtrees (sub-expressions).

Solution Approach

Here is a step-by-step breakdown of the recursive parsing algorithm:

Base Case: If the current expression is just 't' or 'f', return its boolean value.
Operator Detection: The first character of a sub-expression will always be an operator: '!', '&', or '|'.
Argument Splitting: The arguments to the operator are inside parentheses and separated by commas. Because arguments can themselves be expressions, we must carefully parse them, tracking parentheses depth to find where each argument ends.
Recursive Evaluation: For each argument, recursively evaluate its value.
Operator Application:
- '!': Apply logical NOT to its single argument.
- '&': Apply logical AND to all arguments (return false if any are false).
- '|': Apply logical OR to all arguments (return true if any are true).
Return the Result: The result of the current sub-expression is returned up the recursion.

This approach is efficient because each character is processed only as needed, and recursion naturally handles the nesting.

Example Walkthrough

Let's walk through the evaluation of expression = "&(|(f),!(f))":

The outermost operator is '&', with two arguments: |(f) and !(f).
First argument: |(f)
- Operator is '|', argument is 'f'
- Evaluate 'f' as false
- OR of [false] is false
Second argument: !(f)
- Operator is '!', argument is 'f'
- Evaluate 'f' as false
- NOT of false is true
AND of [false, true] is false
Return false as the final result.

Time and Space Complexity

Brute-force: Searching for innermost parentheses and replacing them repeatedly could lead to O(N²) time in the worst case, where N is the length of the expression, due to repeated string manipulations.
Optimized Recursive Approach:
- Time Complexity: O(N), since each character is processed at most once during parsing and evaluation.
- Space Complexity: O(N), due to the recursion stack and temporary storage for arguments.
The recursive approach is both time and space efficient for the problem constraints.

Summary

This problem is an exercise in recursive parsing and evaluation of boolean expressions. By recognizing the tree-like, nested structure, we can design a recursive solution that is both concise and efficient. The key insight is to treat each operator and its arguments as a subproblem, delegating the evaluation of sub-expressions to recursive calls. This leads to clean code that naturally handles all levels of nesting and operator precedence.

AlgoMap.io

Want Help Cracking FAANG?