/**
布爾表達(dá)式 是計(jì)算結(jié)果不是 true 就是 false 的表達(dá)式。有效的表達(dá)式需遵循以下約定：

't'，運(yùn)算結(jié)果為 true
'f'，運(yùn)算結(jié)果為 false
'!(subExpr)'，運(yùn)算過程為對(duì)內(nèi)部表達(dá)式 subExpr 進(jìn)行 邏輯非（NOT）運(yùn)算
'&(subExpr1, subExpr2, ..., subExprn)'，運(yùn)算過程為對(duì) 2 個(gè)或以上內(nèi)部表達(dá)式 subExpr1, subExpr2, ..., subExprn 進(jìn)行 邏輯與（AND）運(yùn)算
'|(subExpr1, subExpr2, ..., subExprn)'，運(yùn)算過程為對(duì) 2 個(gè)或以上內(nèi)部表達(dá)式 subExpr1, subExpr2, ..., subExprn 進(jìn)行 邏輯或（OR）運(yùn)算
給你一個(gè)以字符串形式表述的 布爾表達(dá)式 expression，返回該式的運(yùn)算結(jié)果。

題目測(cè)試用例所給出的表達(dá)式均為有效的布爾表達(dá)式，遵循上述約定。

來源：力扣（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' 和 ',' 之一

來源：力扣（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;
            
    }
};