1106

1106. Parsing A Boolean Expression (Hard)

Return the result of evaluating a given boolean expression, represented as a string.

An expression can either be:

• "t", evaluating to True;
• "f", evaluating to False;
• "!(expr)", evaluating to the logical NOT of the inner expression expr;
• "&(expr1,expr2,...)", evaluating to the logical AND of 2 or more inner expressions expr1, expr2, ...;
• "|(expr1,expr2,...)", evaluating to the logical OR of 2 or more inner expressions expr1, expr2, ...

 

Example 1:

Input: expression = "!(f)"
Output: true

Example 2:

Input: expression = "|(f,t)"
Output: true

Example 3:

Input: expression = "&(t,f)"
Output: false

Example 4:

Input: expression = "|(&(t,f,t),!(t))"
Output: false

 

Constraints:

• 1 <= expression.length <= 20000
• expression[i] consists of characters in {'(', ')', '&', '|', '!', 't', 'f', ','}.
• expression is a valid expression representing a boolean, as given in the description.

Related Topics:
String

Solution 1.

// OJ: https://leetcode.com/problems/parsing-a-boolean-expression/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(H) where H is the maximum depth of the expression
class Solution {
    int i = 0;
    bool dfs(string &s) {
        if (s[i] == 't' || s[i] == 'f') return s[i++] == 't';
        char op = s[i++];
        ++i; // (
        bool ans;
        if (op == '!') ans = !dfs(s);
        else {
            ans = op == '&';
            while (s[i] != ')') {
                if (s[i] == ',') ++i;
                if (op == '&') ans = dfs(s) && ans;
                else ans = dfs(s) || ans;
            }
        }
        ++i; // )
        return ans;
    }
public:
    bool parseBoolExpr(string s) {
        return dfs(s);
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/parsing-a-boolean-expression/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(H) where H is the maximum depth of the expression
class Solution {
public:
    bool parseBoolExpr(string s) {
        stack<char> op;
        stack<bool> ans;
        int i = 0, N = s.size();
        while (i < N) {
            if (s[i] == 't' || s[i] == 'f') ans.push(s[i++] == 't');
            else if (s[i] == '!' || s[i] == '&' || s[i] == '|') {
                op.push(s[i]);
                if (s[i] != '!') ans.push(op.top() == '&');
                i += 2;
            } else if (s[i] == ',' || s[i] == ')') {
                if (op.top() == '&' || op.top() == '|') {
                    bool val = ans.top();
                    ans.pop();
                    if (op.top() == '&') ans.top() = ans.top() && val;
                    else ans.top() = ans.top() || val;
                } else ans.top() = !ans.top();
                if (s[i] == ')') op.pop();
                ++i;
            }
        }
        return ans.top();
    }
};