Leetcode 1197 Solution

This article provides solution to leetcode question 1197 (parsing-a-boolean-expression)
Categories:
Tags:
Access this page by simply typing in "lcs 1197" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/parsing-a-boolean-expression

Solution

class Solution:
    def parseBoolExpr(self, expr: str) -> bool:
        i = 0

        def dfs():
            nonlocal expr
            nonlocal i

            if expr[i] == 't':
                i += 1
                return True
            elif expr[i] == 'f':
                i += 1
                return False
            elif expr[i] == '!':
                i += 2
                ans = not dfs()
                i += 1
                return ans
            elif expr[i] == '&':
                i += 2
                ans = True

                while True:
                    ans &= dfs()

                    if expr[i] == ',':
                        i += 1
                    elif expr[i] == ')':
                        break
                i += 1
                return ans
            elif expr[i] == '|':
                i += 2
                ans = False

                while True:
                    ans |= dfs()

                    if expr[i] == ',':
                        i += 1
                    elif expr[i] == ')':
                        break
                i += 1
                return ans
            else:
                raise Exception("Unexpected '{}'!".format(expr[i]))

        return dfs()