题目描述

leetcode1106. 解析布尔表达式

给你一个以字符串形式表述的 布尔表达式（boolean） expression，返回该式的运算结果。

有效的表达式需遵循以下约定：

  • "t"，运算结果为 True
  • "f"，运算结果为 False
  • "!(expr)"，运算过程为对内部表达式 expr 进行逻辑 非的运算（NOT）
  • "&(expr1,expr2,...)"，运算过程为对 2 个或以上内部表达式 expr1, expr2, ... 进行逻辑 与的运算（AND）
  • "|(expr1,expr2,...)"，运算过程为对 2 个或以上内部表达式 expr1, expr2, ... 进行逻辑 或的运算（OR）

 

示例 1：

输入：expression = "!(f)"
输出：true

示例 2：

输入：expression = "|(f,t)"
输出：true

示例 3：

输入：expression = "&(t,f)"
输出：false

示例 4：

输入：expression = "|(&(t,f,t),!(t))"
输出：false

 

提示：

  • 1 <= expression.length <= 20000
  • expression[i] 由 {'(', ')', '&', '|', '!', 't', 'f', ','} 中的字符组成。
  • expression 是以上述形式给出的有效表达式，表示一个布尔值。

题解——递归分治，20行完事。

递归方法，码量小，但空间消耗比较大。

思路

观察表达式，其实具有统一形式，即单个t/f或者*(e1,e2,...)，其中，代表运算符，ei代表子表达式。所以，对于每一个表达式，我们可以*逐个计算它的子表达式，并进行合并。

考虑如何拆分：如果只有一个字符，直接返回ture/false，如果首个字符是!，计算去掉括号的部分，取反返回即可。这都比较容易。

如果是&，考虑子表达式的判定方法。首先，子表达式结尾的下一个字符一定是,或者)，不过这还不是充分条件，还得要求括号嵌套深度为0(不算最外层的括号)，这样，我们计算的才是当前的子表达式，而不会是子表达式的子表达式。体现在代码上，就是维护一个depth，遇到左括号+1，遇到右括号-1，如果depth为0且下一个字符满足条件，截取并计算一个子表达式，并更新下一个子表达式的begin。同时不断地与ans进行运算。

值得一提的是，如果进行与运算，就将ans初始化为true，进行或运算，就初始化为false，这才能不影响结果。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool parseBoolExpr(string expression) {
        if(expression.size()==1)//递归终点
            return expression=="t"?true:false;
        if(expression[0]=='!')//非运算，去掉外层括号，对计算结果取反
            return !parseBoolExpr(expression.substr(2,expression.size()-3));
        int isAnd=expression[0]=='&',ans=isAnd,depth=0,beg=2;//用isAnd标志进行的是&还是|
        for(int now=2;now<expression.size()-1;++now)
        {
            depth+=expression[now]=='('?1:expression[now]==')'?-1:0;
            if(depth==0&&(expression[now+1]==','||expression[now+1]==')'))
            {//深度为0，且下一个字符为,或)，截取子表达式，计算并更新ans和beg
                int child=parseBoolExpr(expression.substr(beg,now-beg+1));
                ans=isAnd?(ans&child):(ans|child);
                beg=now+2;//更新beg，要跳过下一个字符
            }
        }
        return ans;
    }
};