Problem 3: Balanced Parentheses (100pts)

Problem

A parenthesis sequence is a string consisting of only left parenthesis ( and right parenthesis ).

A parenthesis sequence is balanced if every left parenthesis has a corresponding right parenthesis and the pairs of parentheses are properly nested. For example, () and (())() are balanced parentheses sequences, while ( and ()())) are not.

Formally, a parentheses sequence s is balanced if one of the following conditions are true:

1. s is empty.
2. s starts with a (, ends with a ), and the rest part of s is balanced. For example, ().
3. s can be divided into two consecutive balanced parentheses sequence. For example, ()(()) is balanced since it can be divided into () and (()).

Write a recursive function balanced that takes a parentheses sequence s and returns whether s is balanced. For example, balanced('()') returns True, while balanced(')') and balanced('(') return False.

括号序列是仅由左括号 ( 和右括号 ) 组成的字符串。

如果每个左括号都有一个对应的右括号，并且括号对正确嵌套，则括号序列是平衡的。 例如，() 和 (())() 是平衡的括号序列，而 ( 和 ()())) 则不是。

形式上，一个括号序列 s 是平衡的，如果满足以下条件之一：

1. s 为空。
2. s 以 ( 开头，以 ) 结尾，且 s 的剩余部分是平衡的。例如，()。
3. s 可以被分成两个连续的平衡括号序列。例如，()(()) 是平衡的，因为它可以被分成 () 和 (())。

编写一个递归函数 balanced，它接受一个括号序列 s，并返回 s 是否平衡。 例如，balanced('()') 返回 True，而 balanced(')') 和 balanced('(') 返回 False。

def divide(s, k):
    """Divide the given parentheses sequence s into two parts at position k.

    >>> left, right = divide('()()', 2)
    >>> left
    '()'
    >>> right
    '()'
    >>> left, right = divide('(())()', 4)
    >>> left
    '(())'
    >>> right
    '()'
    >>> left, right = divide('(())()', 6)
    >>> left
    '(())()'
    >>> right
    ''
    """
    COOP[SECRET[0]].append("divide")  # Records the usage of this function
    return (s[:k], s[k:])


def peel(s):
    """Peel off the leftmost and rightmost parentheses in s to obtain the
    internal part of the parentheses sequence.

    >>> peel('(())')
    '()'
    >>> peel('()')
    ''
    >>> peel('))((')
    ')('
    """
    COOP[SECRET[0]].append("peel")  # Records the usage of this function
    return s[1:-1]


def match(s):
    """Returns whether the leftmost and the rightmost parentheses in s match.

    >>> match('()')
    True
    >>> match('()()')
    True
    >>> match('()))')
    True
    >>> match('))')
    False
    >>> match(')())')
    False
    """
    COOP[SECRET[0]].append("match")  # Records the usage of this function
    return s[0] == "(" and s[-1] == ")"


def balanced(s):
    """Returns whether the given parentheses sequence s is balanced.

    >>> SECRET[0] = "SSBsb3ZlIFNJQ1AK"
    >>> COOP[SECRET[0]] = []  # Reset the usage record
    >>> balanced('()')
    True
    >>> balanced(')')
    False
    >>> balanced('(())')
    True
    >>> balanced('()()')
    True
    >>> balanced('()())')
    False
    >>> balanced('()(()')
    False
    >>> t = balanced('()') # balanced must be a pure function
    >>> t
    True
    >>> # You should use divide, peel, and match in your implementation
    >>> assert COOP["SSBsb3ZlIFNJQ1AK"], "Do not steal chicken!"
    """
    "*** YOUR CODE HERE ***"

Hints

• Hint1: Read the docstring of the three given helper functions divide, peel and match, and try to make the best use of them.
• Hint2: Don't be afraid to use loops when you have to!
• Hint3: You must use all three helper functions in your implementation. Do not make any assumptions about their implementation details!

• 阅读三个给定的辅助函数 divide、peel 和 match 的文档字符串，并尝试充分利用它们。

• 在必要时不要害怕使用循环！

• 你的实现中必须使用所有这三个辅助函数。不要对它们的实现细节做任何假设！

• OJ 的输入非常简单，复杂情况没有考虑到，所以就算你过了 OJ，答案也有可能是错的。

Solutions

一个非空平衡序列 s 要么是 (A) 形式，要么是 AB 形式（A 和 B 都是平衡序列）。

def balanced(s):
    if s == "":
        # 基础情况 1：空字符串是平衡的。
        return True

    # 检查是否满足 (A) 形式：s 以 '(' 开始，以 ')' 结束，且内部部分 A 也是平衡的。
    elif match(s) and balanced(peel(s)):
        # match(s): 检查 s 的首尾括号是否匹配。
        # peel(s): 移除 s 的首尾括号，得到内部的子序列 A。
        # balanced(peel(s)): 递归检查子序列 A 是否平衡。
        return True

    """
    注意：此处不能写成以下形式：
    elif match(s):
        return balanced(peel(s))
    错误原因：考虑输入 "()()"
    """

    # 如果不是 (A) 结构，就尝试 A B 结构：s = A + B，其中 A 和 B 都是平衡序列。
    else:
        # k 是分割点的位置
        k = 1 
        left, right = divide(s, k)

        # 循环尝试所有可能的分割点 k，直到右半部分 right 变为空。
        while right != "":

            # 检查 A 和 B 是否都平衡。
            if balanced(left) and balanced(right):
                # 找到一个有效的分解 s = A B，其中 A 和 B 都是平衡的。
                return True

            # 如果没找到，就移动到下一个分割点
            k += 1
            left, right = divide(s, k)

    # 如果以上所有情况（空、(A) 结构、所有可能的 AB 结构）都无法满足，则 s 不平衡。
    return False