一个程序应该用Python编写所有正确的parantheses

Question

我正在尝试编写一个程序(对于给定的自然n,不超过50):

• 2n写出正确的括号的所有可能组合,这意味着在输出的每一行都有一系列具有这些属性的括号:

  • 序列具有n开放,n封闭的括号
  • 在任何时候都没有一个未打开的右括号

我在Java中完成了几乎完全相同的代码并且它完美地工作,但不知何故以下代码中断:

MAX = 100;
arr = [];
for i in range(0, MAX):
        arr.append(' ');

def write(n, pos, op, cl):
        if (cl == n):
                for i in range(0, MAX):
                        if arr[i] != ' ':
                                print(arr[i]);
                        else:
                                break;
                print("\n");
        else:
                if (op > cl):
                        arr[pos] = ')';
                        write(n, pos+1, op, cl+1);
                if (op < n):
                        arr[pos] = '(';
                        write(n, pos+1, op+1, cl);

n = raw_input();

write(n, 0, 0, 0);

这个想法很基本,但是当我试图运行它时,我得到一个错误,说明在某些时候声明

arr[pos] = '(';

是非法的,因为变量pos是>= MAX

我还不熟悉Python,但从算法的角度来看,我看不出原因.

我很欣赏任何想法

Answer 1

我正在使用 Python 2.7.9，但基本上你的问题是你正在使用raw_input()，它以字符串的形式获取输入。

如果您只是使用将其转换为整数int()，您的代码将起作用：

MAX = 100;
arr = [];
for i in range(0, MAX):
        arr.append(' ')

def write(n, pos, op, cl):
        if (cl == n):
                for i in range(0, MAX):
                        if arr[i] != ' ':
                                print(arr[i]), #add a comma here
                        else:
                                break;
                print("\n")
        else:
                if (op > cl):
                        arr[pos] = ')'
                        write(n, pos+1, op, cl+1)
                if (op < n):
                        arr[pos] = '('
                        write(n, pos+1, op+1, cl)

n = int(raw_input())  #change the input to an integer

write(n, 0, 0, 0)

另外，我在 print 语句后添加了一个逗号，因此输出如下：

>>> 
3
( ) ( ) ( ) 

( ) ( ( ) ) 

( ( ) ) ( ) 

( ( ) ( ) ) 

( ( ( ) ) )