Return the result of evaluating a given boolean expression, represented as a string.

An expression can either be:


	"t", evaluating to True;
	"f", evaluating to False;
	"!(expr)", evaluating to the logical NOT of the inner expression expr;
	"&amp;(expr1,expr2,...)", evaluating to the logical AND of 2 or more inner expressions expr1, expr2, ...;
	"|(expr1,expr2,...)", evaluating to the logical OR of 2 or more inner expressions expr1, expr2, ...


&nbsp;
Example 1:

Input: expression = "!(f)"
Output: true


Example 2:

Input: expression = "|(f,t)"
Output: true


Example 3:

Input: expression = "&amp;(t,f)"
Output: false


&nbsp;
Constraints:


	1 &lt;= expression.length &lt;= 2 * 104
	expression[i] consists of characters in {'(', ')', '&amp;', '|', '!', 't', 'f', ','}.
	expression is a valid expression representing a boolean, as given in the description.


class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        
        # expresssion map
        opMap = {"!" : "!", "|" : "|" , "&" : "&"}
        expMap = {"t" : True, "f" : False}
        expStack = []
        opStack = []
        ans = 0
        i = 0
        
        while i < len(expression):
            
            if expression[i] in opMap:
                opStack.append(opMap[expression[i]])
            
            elif expression[i] in expMap:
                expStack.append(expMap[expression[i]])
                
            elif expression[i] == "(":
                expStack.append("(")
            
            # strat performing operations
            elif expression[i] == ")":
                op = opStack.pop()
                ans = [] # evaluator arr
                
                # To Check
                # print("EXPSTACK :- ", expStack, "OPSTACK :- ", opStack, "outer WHILE")
                
                # Performing serries of operation on exp inside a ()
                while expStack[-1] != "(":
                    
                    # To check 
                    # print("EXPSTACK :- ", expStack, "OPSTACK :- ", opStack, "OPerator :- ",op, "INNER WHILE")
    
                    # Not single operation only
                    if op == "!":
                        ans.append(not expStack.pop())
                    else:
                        ans.append(expStack.pop())
                
                # Operation evaluation for more then 1 exp inside () for &, or
                while len(ans) > 1:
                    # or
                    if op == "|":
                        exp1, exp2 = ans.pop(), ans.pop()
                        res = exp1 or exp2
                        ans.append(res)
                    # and
                    elif op == "&":
                        exp1, exp2 = ans.pop(), ans.pop()
                        res = exp1 and exp2
                        ans.append(res)
                    
                # poping ")" and adding the res of operation done above
                expStack.pop() # poping ")"
                expStack.append(ans[-1])
                        
            # increment i   
            i += 1
                
        return expStack[-1]
    
    
"""
TC : O(n * m) | n = len(expression), m = no of expression inside a prenthesis
Sc : O(n)
"""
class Solution {
    
    int pos = 0;
    
    public boolean parseBoolExpr(String s) {
        pos = 0;
        return solve(s, '-');
    }
    
    public boolean solve(String s, char prev_sign) {
       
        boolean res = s.charAt(pos) == 'f' ? false : true;
        char cur_sign = ' ';
        int flag_res_init = 0;
        while(pos < s.length()) {
            
            char cur_char = s.charAt(pos++);
            
            if(isExpr(cur_char)){
                res = eval(cur_char == 't'?true:false, res , prev_sign);
            }
            else if(isSign(cur_char)){
                cur_sign = cur_char;
            }
            else if(cur_char == '('){
                if(flag_res_init == 1 || prev_sign == '!')
                    res = eval(solve(s, cur_sign), res, prev_sign);
                else {
                    res = solve(s, cur_sign);
                    flag_res_init = 1;
                }
            }
            else if(cur_char == ')'){
                 return res;
            }
            
        }
       return res;
    }
    
    public boolean isExpr(char c){
        return (c == 'f' || c == 't');
    }
    
    public boolean isSign(char c){
        return (c == '!' || c == '&' || c == '|');
    }
    
    public boolean eval(boolean e1, boolean e2, char sign) {
     
        boolean res = false;
        if(sign == '!')
            res = !e1;
        
        else if(sign == '|')
            res = e1 | e2;
        
        else if(sign == '&')
            res = e1&e2;
        
        return res;
    }
}
class Solution {
    pair<bool,int> dfs(string &e, int idx){
        bool res;
        if(e[idx]=='!'){
            auto [a,b]=dfs(e, idx+2);
            return {!a,b+3};
        }else if(e[idx]=='&'){
            int len=2;
            res=true;
            idx+=2;
            while(e[idx]!=')'){
                if(e[idx]==','){
                    idx++;len++;
                }
                auto [a,b]=dfs(e,idx);
                res&=a;
                idx+=b;
                len+=b;
            }
            return {res,len+1};
        }else if(e[idx]=='|'){
            int len=2;
            res=false;
            idx+=2;
            while(e[idx]!=')'){
                if(e[idx]==','){
                    idx++;len++;
                }
                auto [a,b]=dfs(e,idx);
                res|=a;
                idx+=b;
                len+=b;
            }
            return {res,len+1};
        }else{
            return {e[idx]=='t',1};
        }
    }
public:
    bool parseBoolExpr(string expression) {
        return dfs(expression, 0).first;
    }
};
var parseBoolExpr = function(expression) {
    let sol, stack = [],
        op={t:true, f:false};
    for(let i=0; i<expression.length; i++){
        if(expression[i] != ")"){
            if(expression[i]!==",")stack.push(expression[i]);
        }else{
            let findings = [], ko;;
             while(stack.slice(-1)[0] !== "("){
                findings.push(stack.pop());
            }
            stack.pop();
            let operator = stack.pop();
            if(operator == '|'){
                ko=findings.reduce((a,b)=>(op[a]||op[b]) === true?'t':'f');
            }
            if(operator == '&'){
                ko=findings.reduce((a,b)=>(op[a]&&op[b]) === true?'t':'f');
            }
            if(operator == '!'){
                ko=findings.pop()==='f'?'t':'f';
            }
            stack.push(ko);
        }

    }
    return stack.pop()=='f'?false:true;
};
Parsing A Boolean Expression