题意
给你一个以字符串形式表述的 布尔表达式（boolean） expression，返回该式的运算结果。
有效的表达式需遵循以下约定：
“t”，运算结果为 True
“f”，运算结果为 False
“!(expr)”，运算过程为对内部表达式 expr 进行逻辑 非的运算（NOT）
“&(expr1,expr2,…)”，运算过程为对 2 个或以上内部表达式 expr1, expr2, … 进行逻辑 与的运算（AND）
“|(expr1,expr2,…)”，运算过程为对 2 个或以上内部表达式 expr1, expr2, … 进行逻辑 或的运算（OR）
思路
类似于表达式求值的题目，用栈来求解。
遍历字符串，
如果当前字符是逗号的话，跳过；
如果当前字符不是右括号，将该字符添加到栈里；
如果是右括号，说明要求值了。遍历前面的字符直到遇到左括号，记录t,f的个数。再根据运算符分类讨论。
运算符为!。当f的个数为1时，结果才为t；其余结果为f
运算符为&。当f的个数为0时，结果才为t；其余结果为f
运算符为|。当t的个数为0时，结果才为f；其余结果为t
将结果放入栈里
遍历完成后，如果栈顶字符为t说明表达式值为true
代码
class Solution { public: bool parseBoolExpr(string expression) { stack<char>stk; for(int i=0;i<expression.size();i++){ if(expression[i]==','){ continue; }else if(expression[i]!=')'){ stk.push(expression[i]); }else{ int t=0,f=0; while(stk.top()!='('){ if(stk.top()=='t') t++; else f++; stk.pop(); } stk.pop(); char op = stk.top();stk.pop(); if(op=='!'){ if(f==1) stk.push('t'); else stk.push('f'); }else if(op=='&'){ if(f==0) stk.push('t'); else stk.push('f'); }else if(op=='|'){ if(t==0) stk.push('f'); else stk.push('t'); } } } return stk.top()=='t' ; } };
func parseBoolExpr(expression string) bool { stk := []rune{} for _,val := range expression { if val == ','{ continue } if val != ')' { stk=append(stk,val) continue } t := 0 f := 0 for stk[len(stk)-1] != '(' { ch := stk[len(stk)-1] if ch == 't' { t++ }else{ f++ } stk = stk[:len(stk)-1] } stk = stk[:len(stk)-1] op := stk[len(stk)-1] stk = stk[:len(stk)-1] if op == '!' { if f == 1 { stk = append(stk, 't') }else{ stk = append(stk, 'f') } }else if op == '&' { if f == 0 { stk = append(stk, 't') }else{ stk = append(stk, 'f') } }else if op == '|' { if t == 0 { stk = append(stk, 'f') }else{ stk = append(stk, 't') } } } return stk[len(stk)-1] == 't' }
