Dynamic programming implementation for （（）（））

gistfile1.py

# !/usr/bin/python
# -*- encoding: utf-8 -*-

import sys

array = list(sys.argv[1])
l = len(array)
dp = []
for i in range(l):
    dp.append([])
    for j in range(l):
        dp[i].append(False)
dp[0][0] = False
for i in range(1, l):
    dp[i][i] = False
    if array[i - 1] == '(' and array[i] == ')':
        dp[i - 1][i] = True
    else:
        dp[i - 1][i] = False

for i in range(l - 2, -1, -1):
    for j in range(i + 2, l):
        ret = False
        if array[i] == '(' and array[j] == ')':
            ret |= dp[i + 1][j - 1]
        for k in range(i + 1, j):
            ret |= (dp[i][k] & dp[k + 1][j])
        dp[i][j] = ret
print dp[0][l - 1]

for item in dp:
    print item