import functools

class Solution:
    def scoreOfParentheses(self, S: str) -> int:
        @functools.lru_cache(maxsize=None)
        def compute(s: str) -> int:
            if len(s) <= 2:
                return 1 if s == "()" else None  # rule #1
            if s.startswith(")") or s.endswith("("):
                return None

            score = compute(s[1:-1])
            if score is not None:
                return 2 * score  # rule #3

            for i in range(2, len(s) - 1, 2):
                score = compute(s[:i])
                if score is None:
                    continue
                score2 = compute(s[i:])
                if score2 is None:
                    continue
                return score + score2  # rule #2

        return compute(S)