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