在python中打印有效的括号组合

Question

我试图用自己的直觉在python中打印所有有效的括号组合.它几乎可以工作,但只是它不会打印几个组合.代码看起来像这样

solution = ""

def parentheses(n):

    global solution

    if n == 0:
        print solution
        return

    for i in range(1, n+1):
        start_index = len(solution)
        solution = solution + ( "(" * i + ")" * i )
        parentheses(n - i)
        solution = solution[:start_index]

if __name__ == "__main__":
    n = int(raw_input("Enter the number of parentheses:"))
    print "The possible ways to print these parentheses are ...."
    parentheses(n)

对于n = 3,它打印

()()()
()(())
(())()
((()))

它的工作原理如下.

在第一次迭代中

()()()将被打印,当调用返回到直接父级时,它将首先开始附加的列表的切片现在将是()并运行循环的下一次迭代以打印()( ( ) ) 等等

问题是我在某种程度上无法使用此逻辑捕获此组合

(()())

虽然我正在考虑如何解决它,如果任何python大师可以建议修复它,那将是伟大的.有其他解决方案,但由于我非常接近,我想改进我的.

Answer 1

我认为您当前版本的逻辑有点过于简单化，无法捕获所有可能性。

这个问题可以归结为 3 种不同的情况：

1. 我们已经使用了所有的左括号，只需要关闭它们
2. 我们当前没有任何左括号，需要在再次关闭之前添加一个
3. 我们至少有一个打开的状态，可以打开一个新的，也可以关闭一个。

为了遵循这个逻辑，我们需要跟踪剩下要使用的开括号数量（no如下）、当前的括号字符串以及开括号与闭括号的当前平衡（curb如下）：

def parens(no, s="", curb=0):
    # case 1: all open parens used
    if no == 0: 
        if curb == 0: 
            return [s]
        return parens(no, s+")", curb-1) 

    # case 2: none are currently open
    if curb == 0:
        return parens(no-1, s+"(", curb+1)

    # case 3: one or more are currently open
    return parens(no-1, s+"(", curb+1) + parens(no, s+")", curb-1)