Parsing A Boolean Expression

Problem Id: 1106 Difficulty: Hard


Intuition

Solution


class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        i = 0
        stack = []
        oper = None
        value = None
        while i < len(expression):
            c = expression[i]
            if c == '&':
                i += 2
                stack.append((oper, value))
                oper = '&'
                value = True
            elif c == '|':
                i += 2
                stack.append((oper, value))
                oper = '|'
                value = False
            elif c == '!':
                i += 2
                stack.append((oper, value))
                oper = '!'
                value = None
            elif c == 't' or c == 'f':
                cur = (c == 't')
                if oper == '&':
                    value = value and cur
                elif oper == '|':
                    value = value or cur
                elif oper == '!':
                    value = not cur
                elif oper == None:
                    value = cur
                i += 1
            elif c == ',':
                i += 1
            elif c == ')':
                cur = value
                oper, value = stack.pop()
                if oper == '&':
                    value = value and cur
                elif oper == '|':
                    value = value or cur
                elif oper == '!':
                    value = not cur
                elif oper == None:
                    value = cur
                i += 1
        return value