这段代码是如何工作的？来自 Codewars 的所有平衡排列

Question

我在codewars中遇到了这个问题，我不明白其他用户的解决方案。

这就是问题

Write a function which makes a list of strings representing all of the ways you can balance n pairs of parentheses

Examples
balanced_parens(0) => [""]
balanced_parens(1) => ["()"]
balanced_parens(2) => ["()()","(())"]
balanced_parens(3) => ["()()()","(())()","()(())","(()())","((()))"]

我的解决方案涉及使用 itertools 排列从输入中获取所有排列并将它们添加到列表中。然而，一旦 n 达到 10，这将消耗太多内存。

这是另一个用户的解决方案。

def balanced_parens(n):
    '''
    To construct all the possible strings with n pairs of balanced parentheses
    this function makes use of a stack of items with the following structure:
        (current, left, right)
    Where:
        current is the string being constructed
        left is the count of '(' remaining
        right is the count of  ')' remaining
    '''
    stack = [('', n, 0)]
    result = []

    # Loop until we run out of items in the stack
    while stack:
        current, left, right = stack.pop()

        # if no '(' or ')' left to add, add current to the result
        if left == 0 and right == 0:
            result.append(current)

        # if we can, add a '(' and return to the stack
        if left > 0:
            stack.append((current + '(', left - 1, right + 1))

        # if we can, add a ')' and return to the stack
        if right > 0:
            stack.append((current + ')', left, right - 1))

    return result

我不明白这段代码将如何循环所有排列。

根据我的理解，我知道这段代码会在循环中添加一个“(”，当有一个开放的“(”时，会添加一个“)”。所以n=3将返回“()()()”

但是它如何循环其余部分，例如“((()))”？

我尝试浏览评论来寻找这个答案。除了说这是一个非常优雅的解决方案之外，没有多说什么。我也无法从chatgpt中理解太多。

Answer 1

该解决方案做了一些事情：

• 它认识到

  (

  的数量与

  )

  的数量相匹配，因此它会跟踪要添加的

  (

  数量，并在每次添加

  )

  时将要添加的

  (

  数量加一.
• 它从左到右构建解决方案，并且对于每个位置，如果还有

  (

  需要添加，则在堆栈中添加

  (

  的延续，如果还有

  )

  需要添加，则添加

  )

  的延续.
• 它会循环直到堆栈为空，这会在

  left

  和

  right

  都为 0 的每个括号组合之后发生 - 也就是说，所有需要的

  (

  都已添加，并且没有剩下

  )

  添加其中之一。

如果您在

stack

== 3 的迭代过程中跟踪

n

：

[('', 3, 0)]
[('(', 2, 1)]
[('((', 1, 2), ('()', 2, 0)]
[('((', 1, 2), ('()(', 1, 1)]
[('((', 1, 2), ('()((', 0, 2), ('()()', 1, 0)]
[('((', 1, 2), ('()((', 0, 2), ('()()(', 0, 1)]
[('((', 1, 2), ('()((', 0, 2), ('()()()', 0, 0)]
[('((', 1, 2), ('()((', 0, 2)]  # '()()()' to result
[('((', 1, 2), ('()(()', 0, 1)]
[('((', 1, 2), ('()(())', 0, 0)]
[('((', 1, 2)]  # '()(())' to result
[('(((', 0, 3), ('(()', 1, 1)]
[('(((', 0, 3), ('(()(', 0, 2), ('(())', 1, 0)]
[('(((', 0, 3), ('(()(', 0, 2), ('(())(', 0, 1)]
[('(((', 0, 3), ('(()(', 0, 2), ('(())()', 0, 0)]
[('(((', 0, 3), ('(()(', 0, 2)]  # '(())()' to result
[('(((', 0, 3), ('(()()', 0, 1)]
[('(((', 0, 3), ('(()())', 0, 0)]
[('(((', 0, 3)]  # '(()())' to result
[('((()', 0, 2)]
[('((())', 0, 1)]
[('((()))', 0, 0)]
[]  # '((()))' to result

所以，结果将是：

['()()()', '()(())', '(())()', '((()))']

您可以看到这对于任何

n

如何工作。

它很优雅，因为代码只有清晰的指令，可以系统地解决所有解决方案，不需要递归（因此对于大

n

来说是安全的），并且结果是可预测的。它不一定是最快或最有效的解决方案 - 但可读的代码通常比高效的代码更好。