1106.md

1106. Parsing A Boolean Expression

Solution 1 (time O(n), space O(n))

class Solution(object):
    def parseBoolExpr(self, expression):
        """
        :type expression: str
        :rtype: bool
        """
        s = []
        for c in expression:
            if c == ",":
                continue
            if c != ")":
                s.append(c)
                continue
            cur_t, cur_f = 0, 0
            while s[-1] != "(":
                if s.pop() == "t":
                    cur_t += 1
                else:
                    cur_f += 1
            s.pop()
            op = s.pop()
            if op == "!":
                s.append("t" if cur_f == 1 else "f")
            elif op == "&":
                s.append("t" if cur_f == 0 else "f")
            elif op == "|":
                s.append("t" if cur_t else "f")
        return s[-1] == "t"