/**
布爾表達(dá)式 是計(jì)算結(jié)果不是 true 就是 false 的表達(dá)式栖袋。有效的表達(dá)式需遵循以下約定：
't'，運(yùn)算結(jié)果為 true
'f'抚太，運(yùn)算結(jié)果為 false
'!(subExpr)'塘幅，運(yùn)算過(guò)程為對(duì)內(nèi)部表達(dá)式 subExpr 進(jìn)行 邏輯非（NOT）運(yùn)算
'&(subExpr1, subExpr2, ..., subExprn)'，運(yùn)算過(guò)程為對(duì) 2 個(gè)或以上內(nèi)部表達(dá)式 subExpr1, subExpr2, ..., subExprn 進(jìn)行 邏輯與（AND）運(yùn)算
'|(subExpr1, subExpr2, ..., subExprn)'尿贫，運(yùn)算過(guò)程為對(duì) 2 個(gè)或以上內(nèi)部表達(dá)式 subExpr1, subExpr2, ..., subExprn 進(jìn)行 邏輯或（OR）運(yùn)算
給你一個(gè)以字符串形式表述的 布爾表達(dá)式 expression电媳，返回該式的運(yùn)算結(jié)果。
題目測(cè)試用例所給出的表達(dá)式均為有效的布爾表達(dá)式庆亡，遵循上述約定匾乓。
來(lái)源：力扣（LeetCode）
示例 1：
輸入：expression = "&(|(f))"
輸出：false
解釋：
首先，計(jì)算 |(f) --> f 又谋，表達(dá)式變?yōu)?"&(f)" 拼缝。
接著，計(jì)算 &(f) --> f 搂根，表達(dá)式變?yōu)?"f" 珍促。
最后，返回 false 剩愧。
示例 2：
輸入：expression = "|(f,f,f,t)"
輸出：true
解釋：計(jì)算 (false OR false OR false OR true) 猪叙，結(jié)果為 true 。
示例 3：
輸入：expression = "!(&(f,t))"
輸出：true
解釋：
首先，計(jì)算 &(f,t) --> (false AND true) --> false --> f 穴翩，表達(dá)式變?yōu)?"!(f)" 犬第。
接著，計(jì)算 !(f) --> NOT false --> true 芒帕，返回 true 歉嗓。
提示：
1 <= expression.length <= 2 * 104
expression[i] 為 '('、')'背蟆、'&'鉴分、'|'、'!'带膀、't'志珍、'f' 和 ',' 之一
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/parsing-a-boolean-expression
**/
#define BOOL(c) ( c=='t'?1:0)
#define FLAG(_logic) ( _logic=='&'?AND:_logic=='|'?OR:NOT)
#define XORANDNOT(_a,_b,_flag) (_flag==AND?_a&&_b:(_flag==OR?_a|_b:!_b))
class Solution {
public:
bool parseBoolExpr(string expression) {
stack<int> stk;
//輔助棧
stack<int> helper;
const int AND=2/*&*/,OR=3/*OR*/,NOT=4/*!*/;
for(auto _logic:expression){
if(_logic=='|'||_logic=='&'||_logic=='!'){
stk.push(FLAG(_logic));
helper.push(FLAG(_logic));
continue;
}
if(_logic=='('||_logic==','){
continue;
}
if(_logic=='f'||_logic=='t'){
stk.push(BOOL(_logic));
continue;
}
int _flag=helper.top();
bool _a=_flag==AND?true:false;
helper.pop();
while(!stk.empty()){
int _b=stk.top();
stk.pop();
if(_b==_flag)stk.push(_a),break;
_a=XORANDNOT(_a,_b,_flag);
}
}
return stk.top()&1;
}
};
