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;
        }
    }
    
  • // 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);
        }
    };
    
  • # 1106. Parsing A Boolean Expression
    # https://leetcode.com/problems/parsing-a-boolean-expression/
    
    class Solution:
        def parseBoolExpr(self, expression: str) -> bool:
            stack = []
            
            for c in expression:
                if c == ")":
                    seen = set()
                    while stack and stack[-1] != "(":
                        seen.add(stack.pop())
                    stack.pop()
                    operator = stack.pop()
                    stack.append(all(seen) if operator == "&" else any(seen) if operator == "|" else not seen.pop())
                elif c != ",":
                    stack.append(True if c == 't' else False if c == 'f' else c)
            
            return stack.pop()
    
    

All Problems

All Solutions