1106. Parsing A Boolean Expression

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 同步地址:

https://github.com/grandyang/leetcode/issues/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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation