1106. 解析布尔表达式
原题
给你一个以字符串形式表述的布尔表达式 expression，返回该式的运算结果。有效的表达式遵循以下约定：
- "t"，运算结果为 True；
- "f"，运算结果为 False;
- "!(expr)"，运算过程为对内部表达式 expr 进行逻辑非（NOT）运算；
- "&(expr1,expr2,...)"，运算过程为对 2 个或以上内部表达式 expr1, expr2, ... 进行逻辑与（AND）运算；
- "|(expr1,expr2,...)"，运算过程为对 2 个或以上内部表达式 expr1, expr2, ... 进行逻辑或（OR）运算
示例 1：
|
1 2 3 |
输入：expression = "!(f)" 输出：true |
示例 2：
|
1 2 3 |
输入：expression = "|(f,t)" 输出：true |
示例 3：
|
1 2 3 |
输入：expression = "&(t,f)" 输出：false |
示例 4：
|
1 2 3 |
输入：expression = "|(&(t,f,t),!(t))" 输出：false |
提示：
+ 1 <= expression.length <= 20000
+ expression[i] 由 {'(', ')', '&', '|', '!', 't', 'f', ','} 中的字符组成。
+ expression 是以上述形式给出的有效表达式，表示一个布尔值。
解题
这里利用堆栈来做, 其实不难, 用ex保存整个计算过程, subEx 保存当前子串的计算过程, 最终拼接成答案
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
class Solution { public: bool parseBoolExpr(string expression) { if(expression.length() <= 0) return false; stack<char> ex; for(int i=0; i<expression.length(); i++) { // cout<<"current char: "<<expression[i]<<endl; if(expression[i] != ')') { // cout<<"push :"<<expression[i]<<endl; ex.push(expression[i]); }else { cout<<ex.top()<<endl; stack<char> subEx; while(ex.top() != '(') { if(ex.top() != ',') subEx.push(ex.top()); ex.pop(); } // pop '(' ex.pop(); char op = ex.top(); ex.pop(); char curRes = calculate(op, subEx); cout<<"curRes "<<curRes<<endl; ex.push(curRes); } } return ex.top() == 't' ? true : false; } // expression[i] != '&' || expression[i] != '|' || expression[i] != '!' char calculate(char op, stack<char> ex) { if(op == '&') { while(!ex.empty()) { if(ex.top() == 'f') return 'f'; ex.pop(); } return 't'; }else if(op == '|') { while(!ex.empty()) { if(ex.top() == 't') return 't'; ex.pop(); } return 'f'; }else if(op == '!') { return ex.top() == 't' ? 'f' : 't'; }else { return false; } } }; |
