【力扣】1106. 解析布尔表达式（C++/Go 栈的应用）
题意
给你一个以字符串形式表述的 布尔表达式（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
}