题目描述

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;
}
};