Problem statement

/

Solution

Similar to BinarySearch 0148 S-Expression Evaluation. Here again create dict of correspondences of brackets d. Then we use part(i) function which will collect either (...) or true, false, or or and. Thene we use dp(i), which will consist of 3 parts: part1, x, part2 or it has only one part1.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, s):
        def corr(s):
            stack, d = [], {}
            for i, elem in enumerate(s):
                if elem == "(":
                    stack.append(i)
                elif elem == ")":
                    last = stack.pop()
                    d[last] = i
            return d

        s = s.replace("true", "1").replace("false", "0")

        def op(x, y, o):
            if o == "or":
                return "1" if x == "1" or y == "1" else "-"
            return "1" if x == "1" and y == "1" else "0"

        def part(i):
            if s[i] == "(":
                return (dp(i + 1), d[i] + 1)
            else:
                j = i
                while j + 1 < len(s) and s[j + 1].isalpha(): j += 1
                return (s[i: j+1], j + 1)

        def dp(i):
            part1, idx = part(i)
            if idx == len(s): return part1
            x, idx = part(idx + 1)
            part2, _ = part(idx + 1)
            return op(part1, part2, x)

        d = corr(s)
        return True if dp(0) == "1" else False