Formatted question description: https://leetcode.ca/all/1106.html

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/

// 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/

// 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();
    }
};

Java

class Solution {
    public boolean parseBoolExpr(String expression) {
        Stack<Character> stack = new Stack<Character>();
        int length = expression.length();
        for (int i = 0; i < length; i++) {
            char c = expression.charAt(i);
            if (c == ',')
                continue;
            else if (c == ')') {
                int tCount = 0, fCount = 0;
                while (stack.peek() != '(') {
                    char prevC = stack.pop();
                    if (prevC == 't')
                        tCount++;
                    else if (prevC == 'f')
                        fCount++;
                }
                stack.pop();
                char operator = stack.pop();
                if (operator == '!') {
                    if (tCount == 1)
                        stack.push('f');
                    else
                        stack.push('t');
                } else if (operator == '&') {
                    if (fCount == 0)
                        stack.push('t');
                    else
                        stack.push('f');
                } else if (operator == '|') {
                    if (tCount == 0)
                        stack.push('f');
                    else
                        stack.push('t');
                }
            } else
                stack.push(c);
        }
        return stack.pop() == 't' ? true : false;
    }
}

All Problems

All Solutions