1106. Parsing A Boolean Expression

class Solution {

    public boolean parseBoolExpr(String expression) 
    {
        
        Stack<Character> stk = new Stack<>();

        for(char curr : expression.toCharArray())
        {
            if(curr == ',' || curr == '(')  continue;

            if(
                curr == 't' || curr == 'f' ||
                curr == '!' || curr == '&' || 
                curr == '|' ) 
            {
                stk.push(curr);

            }
            else if(curr == ')')
            {
                boolean iftrue = false, iffalse = false;

                while(stk.peek() != '!' && stk.peek() != '&' && stk.peek() != '|')
                {
                    char val = stk.pop();
                    if(val == 't')  iftrue = true;
                    if(val == 'f')  iffalse = true;

                }

                char op = stk.pop();
                if(op == '!')
                {
                    stk.push(iftrue ? 'f' : 't');

                }
                else if(op == '&')
                {
                    stk.push(iffalse ? 'f' : 't');

                }
                else
                {
                    stk.push(iftrue ? 't' : 'f');
                } 

            }

        
        
        }

        return stk.peek() == 't';
        
    }


/*

    RUNTIME 6 MS, MEMORY 44.43 MB



    public boolean parseBoolExpr(String expression) 
    {
        return dfs(expression, 0, expression.length() - 1);

        
    }


    public boolean dfs(String expression, int s, int e) //start, end
    {

        if(s ==e)
        {
            return expression.charAt(s) == 't';
        }

        ArrayList<Boolean> exps = new ArrayList<>();
        int layer = 0; int left = 0;
        char op = ' ';

        for(int i = s; i <= e; i++) 
        {
            char c = expression.charAt(i);

            if(layer == 0 && (c == '!' || c == '&' || c == '|'))
            {
                op = c;
            }
            else if(c == '(' && ++layer == 1)
            {
                left = i + 1;
            }
            else if(c == ')' && --layer == 0)
            {
                exps.add(dfs(expression, left, i - 1));
            }
            else if(c == ',' && layer == 1) 
            {
                exps.add(dfs(expression, left, i - 1));
                left = i + 1;
            }
        }

        if(op == '&') 
        {
            boolean result = true;
            for(boolean exp : exps)
            {
                result &= exp;
            }

            return result;
        }

        if(op == '|') 
        {
            boolean result = false;
            for(boolean exp : exps)
            {
                result |= exp;
            }
            
            return result;
        }

        return !exps.get(0);

    }


    */
}