Skip to content

Parsing A Boolean Expression⚓︎

Link

Description⚓︎

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:
1
2
3
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:
1
2
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^4
  • expression[i] is one following characters: '(', ')', '&', '|', '!', 't', 'f', and ','.

Solution⚓︎

Way 1⚓︎

See reference 1 and reference 2 (Chinese).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    bool parseBoolExpr(string expression) {
        stack<int> stk;
        for (const char& ch : expression) {
            if (ch == ')') {
                unordered_set<char> s;
                while (stk.top() != '(') {
                    s.insert(stk.top()); stk.pop();
                }
                stk.pop();  // pop '('
                char op = stk.top(); stk.pop();
                if (op == '&') {
                    stk.push(s.count('f') ? 'f' : 't');
                } else if (op == '|') {
                    stk.push(s.count('t') ? 't' : 'f');
                } else { // op == '!'
                    stk.push(s.count('t') ? 'f' : 't');
                }
            } else if (ch != ',') {
                stk.push(ch);
            }
        }
        return stk.top() == 't';
    }
};