[LeetCode] 1106. Parsing A Boolean Expression

[grandyang]

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.

这道题说是给了一个布尔型的表达式，让我们进行解析，并返回最终的值。其中的t和f分别表示 true 和 false，这里还有其他三种操作符，与，或，和非，这些都是最基本的逻辑运算，没有太大的难度。这道题的难点在于给定的是一个字符串，而且可能出现嵌套的运算，比如例子4，运算顺序应该是从内而外的。如何才能拆分出正确的逻辑块并进行运算是一个难点，由于存在嵌套，所以从左到右遍历的话可能会遇到很多的左括号，什么时候知道遇到最内层的逻辑块了呢，就是第一次遇到右括号的时候，这样跟之前一个左括号之间的内容一定是当前最内层的逻辑块了，可以进行计算了。所以右括号的位置是一个触发点，并且需要回溯到前一个左括号的位置，这种后进先出的特点可以使用栈来做。所以大体是思路就有了，遍历表达式的每一个字符，只要遇到的不是右括号或者逗号（逗号入栈没有意义，可以直接忽略），就压入栈。若遇到了右括号，则此时要出栈，直至到上一个左括号，中间的可能有大量的t和f，重复出现的不影响结果，可以将所有内容放入到一个 HashSet 中，这样方便之后查找。当对应的左括号也出栈之后，接下来栈顶的就是操作符了，将其出栈，并且根据其不同进行逻辑运算：若是与运算，则只要看 HashSet 中是否有 false，有的话结果就是 false，压入栈；若是或运算，只要看 HashSet 中是否有 true，有的话就是 true，压入栈。若是非运算，则 HashSet 中只有一个布尔型变量，对其取反并压入栈。最终遍历完成后，栈中只会剩余一个布尔型变量，根据其结果返回对应的 true 或者 false 即可，参见代码如下：

class Solution {
public:
    bool parseBoolExpr(string expression) {
        stack<char> st;
        for (int i = 0; i < expression.size(); ++i) {
            char c = expression[i];
            if (c == ')') {
                unordered_set<char> seen;
                while (!st.empty() && st.top() != '(') {
                    seen.insert(st.top()); st.pop();
                }
                st.pop();
                char op = st.top(); st.pop();
                if (op == '&') {
                    st.push(seen.count('f') ? 'f' : 't');
                } else if (op == '|') {
                    st.push(seen.count('t') ? 't' : 'f');
                } else {
                    st.push(seen.count('t') ? 'f' : 't');
                }
            } else if (c != ',') {
                st.push(c);
            }
        }
        return st.top() == 't';
    }
};

Github 同步地址:

#1106

参考资料：

https://leetcode.com/problems/parsing-a-boolean-expression/

https://leetcode.com/problems/parsing-a-boolean-expression/discuss/323307/Python-Easy-1-line-Cheat

https://leetcode.com/problems/parsing-a-boolean-expression/discuss/323532/JavaPython-3-Iterative-and-recursive-solutions-w-explanation-and-analysis.

LeetCode All in One 题目讲解汇总(持续更新中...)