Leetcode 1106. Parsing A Boolean Expression

Problem

Our task is to evaluate a boolean expression represented as a string. The expression includes "t", "f", "!" (not), "&" (and) and "|" (or). These expressions can also be nested within parentheses.

For example,

• If we have the expression "!(f)", it means NOT false, which evaluates to true.
• If we have the expression "&(t,f)", it means true AND false, which evaluates to false.
• If we have the expression "|(t,f)", it means true OR false, which evaluates to true.

Approach

A typical approach to solve this problem is to use recursion. We start at the beginning of the string and evaluate the expression. If we encounter a 't' or 'f', we return the corresponding boolean value (True or False). If we encounter a '!', '&', or '|', we recursively evaluate the expression within the parentheses.

Specifically:

• If we encounter '!', we calculate the NOT of the expression within the parentheses.
• If we encounter '&', we calculate the AND of all expressions within the parentheses.
• If we encounter '|', we calculate the OR of all expressions within the parentheses.

For example, if we have the expression |(&(t,f,t),!(t)), we first evaluate &(t,f,t), which is false, and then evaluate !(t), which is also false. Finally, we apply OR to the results, yielding false.

Python Solution

1
2python
3class Solution:
4 def parseBoolExpr(self, expression: str) -> bool:
5    def parse(i: int) -> ("result", "next_index"):
6        if expression[i] == 't':
7            return True, i + 1
8        if expression[i] == 'f':
9            return False, i + 1
10        if expression[i] == '!':
11            inner_result, next_index = parse(i + 2)
12            return not inner_result, next_index + 1
13
14        assert(expression[i] in ('&', '|'))
15        results, next_index = [], i + 2
16        while True:
17            if expression[next_index] == ')':
18                break
19            inner_result, next_index = parse(next_index)
20            results.append(inner_result)
21            if expression[next_index] == ',':
22                next_index += 1
23        return (all(results) if expression[i] == '&' else any(results)), next_index + 1
24
25    return parse(0)[0]

Java Solution

1
2java
3class Solution {
4    public boolean parseBoolExpr(String expression) {
5        int[] i = new int[] {0};
6        return parse(expression, i);
7    }
8
9    private boolean parse(String expression, int[] i) {
10        char c = expression.charAt(i[0]++);
11        if (c == 't') return true;
12        if (c == 'f') return false;
13        if (c == '!') {
14            i[0]++; // Skip '('
15            boolean ans = !parse(expression, i);
16            i[0]++; // Skip ')'
17            return ans;
18        }
19        boolean isAnd = c == '&';
20        boolean ans = isAnd;
21        i[0]++; // Skip '('
22        while (true) {
23            if (expression.charAt(i[0]) == ')') break;
24            boolean parsed = parse(expression, i);
25            if (isAnd) ans &= parsed;
26            else ans |= parsed;
27            if (expression.charAt(i[0]) == ',') i[0]++;
28        }
29        i[0]++; // Skip ')'
30        return ans;
31    }
32}

C++ Solution

1
2cpp
3class Solution {
4public:
5    bool parseBoolExpr(string expression) {
6        int i = 0;
7        return parse(expression, i);
8    }
9
10    bool parse(const string& expression, int& i) {
11        if (expression[i] == 't') {
12            ++i;
13            return true;
14        }
15        if (expression[i] == 'f') {
16            ++i;
17            return false;
18        }
19        if (expression[i] == '!') {
20            i += 2; // Skip '('
21            bool ans = !parse(expression, i);
22            ++i; // Skip ')'
23            return ans;
24        }
25
26        bool isAnd = expression[i] == '&';
27        bool ans = isAnd;
28        i += 2; // Skip '('
29        while (expression[i] != ')') {
30            bool parsed = parse(expression, i);
31            if (isAnd) ans &= parsed;
32            else ans |= parsed;
33            if (expression[i] == ',') ++i;
34        }
35        ++i; // Skip ')'
36        return ans;
37    }
38};

JavaScript Solution

1
2javascript
3var parseBoolExpr = function(expression) {
4    var parse = function(i) {
5        var c = expression[i], result = [];
6        i += 2;
7        if (c === '&') {
8            while (expression[i] !== ')') {
9                if (expression[i] === ',') {
10                    i++;
11                } else {
12                    result.push(parse(i));
13                    i += 2;
14                }
15            }
16            return result.every(Boolean);
17        } else if (c === '|') {
18            while (expression[i] !== ')') {
19                if (expression[i] === ',') {
20                    i++;
21                } else {
22                    result.push(parse(i));
23                    i += 2;
24                }
25            }
26            return result.some(Boolean);
27        } else if (c === '!') {
28            return !parse(i);
29        } else {
30            return c === 't';
31        }
32    };
33
34    return parse(0);
35};

C# Solution

1
2CSharp
3public class Solution {
4    public bool ParseBoolExpr(string expression) {
5        int i = 0;
6        return Parse(expression, ref i);
7    }
8    
9    private bool Parse(string expression, ref int i) {
10        char c = expression[i++];
11        if (c == 't') return true;
12        if (c == 'f') return false;
13        if (c == '!') {
14            i++; // Skip '('
15            bool ans = !Parse(expression, ref i);
16            i++; // Skip ')'
17            return ans;
18        }
19        
20        bool isAnd = c == '&';
21        bool ans = isAnd;
22        i++; // Skip '('
23        while (true) {
24            if (expression[i] == ')') break;
25            bool parsed = Parse(expression, ref i);
26            if (isAnd) ans &= parsed;
27            else ans |= parsed;
28            if (expression[i] == ',') i++;
29        }
30        i++; // Skip ')'
31        return ans;
32    }
33}

As shown above, the problem can be approached using recursion in Python, Java, C++, JavaScript or C#. The expressions are parsed through a function which increments index to traverse the string. It checks if the current index element represents a true, false, not, and or or operation and updates the result accordingly.

• For the 'not' operation, we just perform a negation of the parsed result.
• For the 'and' operation, we initialise the result as true and then perform an AND with each parsed result until we encounter a ')'.
• For 'or' operation, we initialise the result as false and then perform an OR operation with each parsed result until we encounter ')'.

While parsing expressions for 'and' or 'or' operation, we skip the ',' character if encountered. After a closing bracket is encountered, we increment the counter to skip over it and return the result.

These solutions demonstrate the power and elegance of recursion to solve problems involving parsing nested expressions. The key challenge in this problem is to keep track of the index while recursively parsing the inner expressions, as well as correctly interpreting and applying the boolean operations represented by '!', '&' and '|'.

While these solutions are already quite efficient, it's always worth considering if the performance could be improved with a different approach, particularly for larger inputs. For example, one potential enhancement could be to use a stack to track and evaluate the nested expressions, which might be more efficient than recursion for deeper inputs.

However, the provided solutions are very readable, offer good performance for typical inputs, and demonstrate some powerful techniques for parsing expressions in various programming languages. Thus, they should serve well in most situations where this kind of task needs to be performed.

Remember, if these solutions are not functioning as expected, make sure to check the input format and parsing function thoroughly as these kinds of bugs are the most common in these scenarios.