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;
"&(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, ...

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

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

Example 3:
Input: expression = "&(t,f)"
Output: false

Example 4:
Input: expression = "|(&(t,f,t),!(t))"
Output: false

 
Constraints:

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

Difficulty: interview

Starter code:

class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        

Solutions:
class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        if expression == 'f':
            return False
        if expression == 't':
            return True
        if expression[0] == '!':
            return not self.parseBoolExpr(expression[2:-1])
        if expression[0] == '|':
            cursor = 2
            while cursor < len(expression)-1:
                end_of_next = self.getNextExpr(expression, cursor)
                if self.parseBoolExpr(expression[cursor:end_of_next]):
                    return True
                cursor = end_of_next + 1
            return False
        if expression[0] == '&':
            cursor = 2
            while cursor < len(expression)-1:
                end_of_next = self.getNextExpr(expression, cursor)
                if not self.parseBoolExpr(expression[cursor:end_of_next]):
                    return False
                cursor = end_of_next + 1
            return True
    
    def getNextExpr(self, expression, start):
        if expression[start] == '!' or expression[start] == '|' or expression[start] == '&':
            open_count = 1
            close_count = 0
            start += 1
            while open_count > close_count:
                start += 1
                if expression[start] == '(':
                    open_count += 1
                if expression[start] == ')':
                    close_count += 1
                
            return start + 1
        else:
            return start + 1

class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        
        bool_stack = []
        expr_stack = []
        
        curr = []
        for char in expression:
            if char == ',':
                continue
            elif char == '(':
                expr_stack.append(curr)
                curr = []
            elif char in 'tf':
                curr.append(True if (char == 't') else False)
            elif char in '|&!':
                bool_stack.append(char)
            else:
                b = bool_stack.pop()
                prev = expr_stack.pop() if expr_stack else []
                if b == '!':
                    curr = prev + [not curr.pop()]
                elif b == '&':
                    curr = prev + [all(curr)]
                else:
                    curr = prev + [any(curr)]
        return curr.pop()

from functools import reduce


class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        def parse_or(*l):
            return reduce(lambda x, y: x or y, l)
        def parse_and(*l): 
            return reduce(lambda x, y: x and y, l)
        def parse_not(x):
            return not x
        
        expression = expression.replace('t', 'True')
        expression = expression.replace('f', 'False')
        
        expression = expression.replace('|', 'parse_or')
        expression = expression.replace('&', 'parse_and')
        expression = expression.replace('!', 'parse_not')

        return eval(expression)

class Solution:

    def get_arg_list(self, s1: List): 
        args = []
        while s1 and isinstance(s1[-1], bool): 
            args.append(s1.pop())
        return args
    
    def boolEval(self, symbol, s1: List):
        if symbol == '!': 
            return not s1[0]
        elif symbol == '&': 
            return all(s1)
        elif symbol == '|': 
            return any(s1)
        else: 
            raise ValueError('Invalid Symbol')
                
    def parseBoolExpr(self, expression: str) -> bool:
        # push ! & | ( onto stack1
        # push t and f onto stack2 
        # pop ( from stack 1 when encounter )
        # if top stack 1 is not paren, then use to evaluate using stack 2
        s1 = []        
        
        for c in expression: 
            if c == '!' or c == '|' or c == '(' or c == '&': 
                s1.append(c)
            elif c == 't' or c == 'f': 
                s1.append(True if c == 't' else False)
            elif c == ')': 
                args = self.get_arg_list(s1)
                s1.pop()
                top = s1[-1]
                while top == '!' or top == '|' or top == '&': 
                    ret = self.boolEval(s1.pop(), args)
                    s1.append(ret)
                    args = self.get_arg_list(s1)
                    top = None if not s1 else s1[-1]
                s1 += args

            elif c == ',': 
                pass
            else: 
                raise ValueError('Invalid character')

        return s1[0]


class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        return eval(expression.translate(str.maketrans({'t': '1', 'f': '0', '!': 'not', '|': 'or_', '&': 'and_'})), {'or_': lambda *a: any(a), 'and_': lambda *a: all(a)})


class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        expression = list(expression)

        def replace_or(start: int):
            braket = 1
            for i in range(start, len(expression)):
                if expression[i] == '(':
                    braket += 1
                elif expression[i] == ')':
                    braket -= 1
                elif braket == 1 and expression[i] == ',':
                    expression[i] = 'or'
                elif braket == 0:
                    break

        for idx, char in enumerate(expression):
            if char == '|':
                expression[idx] = ''
                replace_or(idx + 2)
            elif char == '&':
                expression[idx] = ''
            elif char == 't':
                expression[idx] = 'True'
            elif char == 'f':
                expression[idx] = 'False'
            elif char == '!':
                expression[idx] = 'not'

        expr = ' '.join(expression).replace(',', 'and')

        return eval(expr)


class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        expression = list(expression)
        table = {'|': 'or', '&': 'and', 't': 'True', 'f': 'False'}

        logic = []
        idx, par = 0, True
        while idx < len(expression):
            if expression[idx] in ['&', '|']:
                logic.append(table[expression[idx]])
                expression[idx] = ''
                idx += 2
            elif expression[idx] == '!':
                logic.append('not')
                expression[idx] = 'not'
                idx += 2
            else:
                if not par and logic:
                    logic.pop()
                    par = True

                if expression[idx] in ['t', 'f']:
                    expression[idx] = table[expression[idx]]
                elif expression[idx] == ',':
                    expression[idx] = logic[-1]
                elif expression[idx] == ')':
                    if logic[-1] == 'not':
                        logic.pop()
                    else:
                        par = False

                idx += 1

        return eval(' '.join(expression))


class Solution:
    def parseBoolExpr(self, ex: str) -> bool:
        def recur(i):
            if ex[i] in ('t','f'):
                return True if ex[i]=='t' else False,i+1
            op=ex[i]
            i=i+2
            stack=[]
            while ex[i]!=')':
                if ex[i]==',':
                    i+=1
                    continue
                
                res,i=recur(i)
                stack.append(res)
            
            if op=='&':
                return all(stack),i+1
            elif op=='|':
                return any(stack),i+1
            elif op=='!':
                return not stack[0],i+1
            return res,i+1
        return recur(0)[0]

class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        expression = list(expression)

        def replace(start: int, logical: str):
            braket = 1
            idxs = []
            for i in range(start, len(expression)):
                if expression[i] == '(':
                    braket += 1
                elif expression[i] == ')':
                    braket -= 1
                elif braket == 1 and expression[i] == ',':
                    idxs.append(i)
                elif braket == 0:
                    break

            for i in idxs:
                expression[i] = logical

        for idx, char in enumerate(expression):
            if char == '|':
                expression[idx] = ''
                replace(idx + 2, 'or')
            elif char == '&':
                expression[idx] = ''

        expr = ' '.join(expression).replace('t', 'True').replace('f', 'False').replace('!', 'not').replace(',', 'and')

        return eval(expr)


class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        expression = list(expression)

        def replace(start: int, logical: str):
            braket = 1
            idxs = []
            for i in range(start, len(expression)):
                if expression[i] == '(':
                    braket += 1
                elif expression[i] == ')':
                    braket -= 1
                elif braket == 1 and expression[i] == ',':
                    idxs.append(i)
                elif braket == 0:
                    break

            for i in idxs:
                expression[i] = logical

        for idx, char in enumerate(expression):
            if char == '|':
                expression[idx] = ''
                replace(idx + 2, 'or')
            elif char == '&':
                expression[idx] = ''
            elif char == 't':
                expression[idx] = 'True'
            elif char == 'f':
                expression[idx] = 'False'
            elif char == '!':
                expression[idx] = 'not'

        expr = ' '.join(expression).replace(',', 'and')

        return eval(expr)


class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        exp=collections.deque(expression)
        
        def or_opt(exp):
            exp.popleft() # skip (
            ret=False
            while exp:
                ret |= exp_opt(exp)
                if exp.popleft()==')': return ret
        
        def and_opt(exp):
            exp.popleft() # skip (
            ret=True
            while exp:
                ret &= exp_opt(exp)
                if exp.popleft()==')': return ret
                                
        def exp_opt(exp):
            ch=exp.popleft()
            ret=False
            if ch=='t': ret=True
            elif ch=='f': ret=False
            elif ch=='!': exp.popleft(); ret=not exp_opt(exp); exp.popleft() # remove (,)
            elif ch=='|': ret=or_opt(exp)
            elif ch=='&': ret=and_opt(exp)
            return ret
        
        return exp_opt(exp)    

class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        table = {'|': 'or', '&': 'and', 't': 'True', 'f': 'False', '(': '('}

        expr, logic = [], []
        idx, par = 0, True
        while idx < len(expression):
            if expression[idx] in ['&', '|']:
                logic.append(table[expression[idx]])
            elif expression[idx] == '!':
                logic.append('not')
                expr.append('not')
            else:
                if not par and logic:
                    logic.pop()
                    par = True

                if expression[idx] in ['t', 'f', '(']:
                    expr.append(table[expression[idx]])
                elif expression[idx] == ',':
                    expr.append(logic[-1])
                elif expression[idx] == ')':
                    expr.append(')')
                    if logic[-1] == 'not':
                        logic.pop()
                    else:
                        par = False

            idx += 1

        return eval(' '.join(expr))


class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        
        def split_into_list(expression):
            
            res = []
            depth = 0
            ss = ''
            
            for e in expression:
                if depth == 0 and e == ',':
                    res.append(ss)
                    ss = ''
                
                else:
                    if e == '(':
                        depth += 1
                    elif e == ')':
                        depth -= 1

                    ss += e
                
            res.append(ss)
            
            return res
        
        if expression == 't':
            return True
        if expression == 'f':
            return False
        
        if expression[0] == '!':
            return not self.parseBoolExpr(expression[2:-1])
            
        if expression[0] == '&':
            
            res = True
            for L in split_into_list(expression[2:-1]):
                res &= self.parseBoolExpr(L)
            
            return res
        
        if expression[0] == '|':
            
            res = False
            for L in split_into_list(expression[2:-1]):
                res |= self.parseBoolExpr(L)
            
            return res

class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        if len(expression) == 1:
            return expression == 't'
        op = expression[0]
        boolean_list = []
        level = 0
        start = 2
        for i in range(2, len(expression) - 1):
            ch = expression[i]
            if ch == '(':
                level += 1
            elif ch == ')':
                level -= 1
            elif ch == ',' and level == 0:
                boolean_list.append(self.parseBoolExpr(expression[start:i]))
                start = i+1
            elif ch not in '&|!' and level == 0:
                boolean_list.append(True if ch == 't' else False)
        boolean_list.append(self.parseBoolExpr(expression[start:-1]))
        if op == '!':
            return not boolean_list[0]
        elif op == '&':
            return all(boolean_list)
        else:
            return any(boolean_list)


class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        stack = []
        for ch in expression:
            if ch == ',':
                continue
            if ch != ')':
                stack.append(ch)
            else:
                temp = ''
                while stack[-1] != '(':
                    temp += stack.pop()
                stack.pop()
                if stack[-1] == '&':
                    res = 't' if temp.count('f') == 0 else 'f'
                elif stack[-1] == '|':
                    res = 'f' if temp.count('t') == 0 else 't'
                else:
                    res = 't' if temp == 'f' else 'f'
                stack[-1] = res
        return True if stack[-1] == 't' else False
        
        


class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        def parse(e: str, left, right):
            if right - left == 1: 
                return e[left] == 't'               
            res = e[left] == '&' # only when the first char is '&', ans assigned True.
            level, start = 0, left + 2 # e[left + 1] must be '(', so start from lo + 2 to delimit sub-expression.
            for i in range(left + 2, right):
                if level == 0  and e[i] in [',', ')']: # found a sub-expression.
                    cur = parse(e, start, i) 
                    start = i + 1 
                    if e[left] == '&':
                        res &= cur
                    elif e[left] == '|':
                        res |= cur
                    else: # e[lo] is '!'.
                        res = not cur
                if e[i] == '(':
                    level = level + 1
                elif e[i] == ')':
                    level = level - 1
            return res;        
        
        return parse(expression, 0, len(expression))


from functools import reduce
class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        operations = {
            '|': any,
            '&': all,
            '!': lambda x: not x[0]
        }
        
        def getTokens(expression):
            depth = 0
            token = ''
            for s in expression:
                if s == ',' and depth == 0:
                    yield token
                    token = ''
                    continue
                if s == '(':
                    depth += 1
                elif s == ')':
                    depth -= 1
                token += s
                
            yield token
        
        def evaluate(expression):
            if expression == 't':
                return True
            elif expression == 'f':
                return False
            
            operator = operations[expression[0]]
            values = [evaluate(token) for token in getTokens(expression[2:-1])]
            return operator(values)
            
        return evaluate(expression)

class Solution:
    # https://www.youtube.com/watch?v=y2kFBqj_J08&list=PLLuMmzMTgVK45AiaeeEGGc6xqM6jrlXL4&index=1
    def parseBoolExpr1(self, expression: str) -> bool:
        def helper(queue):
            res = True
            while queue:
                c = queue.pop()
                print(('c = {0}'.format(c)))
                if c in {'t', 'f'}:
                    return True if c == 't' else False
                if c == '!':
                    # remove '('
                    queue.pop()
                    # print('!, queue = {0}'.format(queue))
                    res = not helper(queue)
                    # remove ')'
                    queue.pop()
                    return res
                # elif c in {'&', '|'}:
                    # for &, True & exp1 & exp2, for |, False | exp1 | exp2
                isAnd = True if c == '&' else False
                res = isAnd
                # remove '('
                queue.pop()
                while True:
                    if isAnd:
                        res &= helper(queue)
                    else:
                        res |= helper(queue)
                    # ch can be ')' or ,  e.g \"|(&(t,f,t),!(t))\"
                    print(('isAnd = {0}, queue = {1}, res = {2}'.format(isAnd, queue, res)))
                    ch = queue.pop()
                    print(('after pop char, char = {0}, queue = {1}'.format(ch, queue)))
                    if ch == ')':
                        break
            return res
        
        queue = collections.deque([])
        for c in expression:
            queue.appendleft(c)
        return helper(queue)
                        
        
    # slow, time: O(n^2)
    def parseBoolExpr(self, expression: str) -> bool:
        # j is inclusive
        def helper(exp, i, j):
            if i == j:
                return exp[i] == 't'
            op = exp[i]
            res = op == '&'
            # k starts from '('
            k, count, prev = i + 1, 0, i + 2
            # print('i = {0}, j = {1}'.format(i, j))
            while k <= j:
                c = exp[k]
                if c == '(':
                    count += 1
                elif c == ')':
                    count -= 1
                if (count == 1 and c == ',') or not count:
                    # print('k = {0}, c = {1}, count = {2}, i1 = {3}, j1 = {4}'.format(k, c, count, i + 2, k - 1))
                    val = helper(exp, prev, k - 1)
                    prev = k + 1
                    if op == '!':
                        res = not val
                    elif op == '&':
                        res &= val
                    elif op == '|':
                        res |= val
                k += 1
            # print('i = {0}, j = {1}, res = {2}'.format(i, j, res))
            return res
        
        return helper(expression, 0, len(expression) - 1)
    
    
        # if len(expression) == 1:
        #     return expression == 't'
        # if expression[0] == '!':
        #     return not self.parseBoolExpr(expression[2:-1])
        # op, stack, i = expression[0], [], 2
        # while i < len(expression) - 1:
        #     if expression[i] == 't' or expression[i] == 'f':
        #         stack.append(self.parseBoolExpr(expression[i]))
        #         i += 1
        #     elif expression[i] in {'!', '&', '|'}:
        #         j, count = i + 2, 1
        #         while j < len(expression) - 1:
        #             if expression[j] == '(':
        #                 count += 1
        #             elif expression[j] == ')':
        #                 count -= 1
        #                 if not count:
        #                     stack.append(self.parseBoolExpr(expression[i:j + 1]))
        #                     i = j + 1
        #                     break
        #             j += 1
        #     else:
        #         i += 1
        # if op == '&':
        #     return all(val for val in stack)
        # return any(val for val in stack)


class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        expression = list(expression)

        def replace(start: int, logical: str):
            braket = 1
            idxs = []
            for i in range(start, len(expression)):
                if expression[i] == '(':
                    braket += 1
                elif expression[i] == ')':
                    braket -= 1
                elif braket == 1 and expression[i] == ',':
                    idxs.append(i)
                elif braket == 0:
                    break

            for i in idxs:
                expression[i] = logical

        for idx, char in enumerate(expression):
            if char == '|':
                expression[idx] = ''
                replace(idx + 2, 'or')
            elif char == '&':
                expression[idx] = ''
                replace(idx + 2, 'and')

        expr = ' '.join(expression).replace('t', 'True').replace('f', 'False').replace('!', 'not')

        return eval(expr)


class Solution:
    def parseBoolExpr(self, ex: str) -> bool:
        def recur(i):
            if ex[i] in ('t','f'):
                return True if ex[i]=='t' else False,i+1
            op=ex[i]
            i,stack=i+2,[]
            while ex[i]!=')':
                if ex[i]==',':
                    i+=1
                    continue
                res,i=recur(i)
                stack.append(res)
            if op=='&':
                return all(stack),i+1
            elif op=='|':
                return any(stack),i+1
            elif op=='!':
                return not stack[0],i+1
            return res,i+1
  
        return recur(0)[0]

class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        ops = {'!', '&', '|'}
        
        def parse(start):
            if expression[start] == 'f':
                return False, start + 1
            if expression[start] == 't':
                return True, start + 1
            if expression[start] in ops:
                new_start = start + 2
                vals = set()
                while new_start < len(expression):
                    val, new_start = parse(new_start)
                    vals.add(val)
                    if expression[new_start] == ')':
                        new_start += 1
                        break
                    assert expression[new_start] == ','
                    new_start += 1
                if expression[start] == '!':
                    assert len(vals) == 1
                    return not list(vals)[0], new_start
                if expression[start] == '&':
                    return all(vals), new_start
                return any(vals), new_start
        
        return parse(0)[0]

import operator
from typing import List


class Solution:

    @staticmethod
    def split_by_comma(expression: str) -> List[str]:
        start = 0
        bracket_balance = 0
        answer = []
        for i in range(len(expression)):
            if expression[i] == '(':
                bracket_balance += 1
            if expression[i] == ')':
                bracket_balance -= 1
            if expression[i] == ',' and not bracket_balance:
                answer.append(expression[start: i+1])
                start = i + 1
        answer.append(expression[start:])
        return answer

    def parseBoolExpr(self, expression: str) -> bool:
        if expression.startswith('t'):
            return True
        if expression.startswith('f'):
            return False
        if expression.startswith('!'):
            return not self.parseBoolExpr(expression[2:-1])
        if expression.startswith('|'):
            return any(map(self.parseBoolExpr,
                           self.split_by_comma(expression[2:-1])))
        else:
            return all(map(self.parseBoolExpr,
                           self.split_by_comma(expression[2:-1])))



class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        stack = []
        for c in expression:
            if c not in [',', ')']:
                stack.append(True if c=='t' else False if c=='f' else c)
            elif c == ')':
                seen = set() # capturing only distinct values i.e single 'f' and 't' 
                while stack[-1] != '(':
                    seen.add(stack.pop())
                stack.pop() # removing '('
                operator = stack.pop()
                stack.append(all(seen) if operator == '&' else any(seen) if operator == '|' else not seen.pop() )
        
        return stack[-1]