题目
给你一个以字符串形式表述的 布尔表达式（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
解题
方法一：栈
相当于每个()就进入一个栈
遇到!,|,&后面一定跟着()
然后同时要记录当前栈里面，是否出现t, f
因此可以通过pair来表示一个栈空间内容
其中pair.frist表示 运算符，0,1,2分别表示!,&,|
pair.second表示 状态, 0:表示还没有t或f，1：表示只有t， 2：表示只有f，3：表示既有t也有f ，也就是说可以理解为int的低位的两位，来表示t或者f是否出现
class Solution { public: bool parseBoolExpr(string expression) { stack<pair<int,int>> st;//pair.first 0:! 1:& 2:| pair.second 0：空 1：只有true 2：只有false 3：有true和false st.emplace(1,0);//初始化主栈空间，由于主栈空间只有可能是true或者false，因此用&或者|都行 for(char c:expression){ if(c=='!'||c=='|'||c=='&'){//压栈 if(c=='!') st.emplace(0,0); if(c=='|') st.emplace(2,0); if(c=='&') st.emplace(1,0); }else if(c=='t'){//最低位来记录t出现了 st.top().second|=1; }else if(c=='f'){//到数第二位来记录f出现了 st.top().second|=2; }else if(c=='(') continue; else if(c==')'){ auto [ops,state]=st.top(); st.pop(); if(ops==0){//！运算 if(state==1) st.top().second|=2; else if(state==2) st.top().second|=1; }else if(ops==1){//&运算，出现一个false，就是false if(state==1) st.top().second|=1; else if(state==2||state==3) st.top().second|=2; }else if(ops==2){//|运算，出现一个true，就是true if(state==1||state==3) st.top().second|=1; else if(state==2) st.top().second|=2; } } } return st.top().second==1?true:false; } };
