最长公共子括号序列

#最长公共字括号序列最终版

#1.经过一系列pop和insert操作生成s3（元素换位后生成的所有t的列表）

s0 = list(input())    
l = len(s0)           
#print(l)
k1 = 0
s3 = []
#s0 原始括号序列
#s1 原始括号序列的备份：会被pop掉一个元素
#s2 备份被pop掉一个元素的s1后再在自身的各个位置insert一个元素
#s3 包含所有得到的t
#s4 筛选出不重复的且与原始s0不同的t
for i in range(l):    #遍历s0中各元素，把每个元素都拿出来并插入新位置（这里是所有位置都插了，
                      #因为后面反正会判断重复性），
    s1 = s0.copy()    #s0的备份：s1的初始化，因为每次拿数据都是从最初的s0上拿，所以拿数据之前的s0要保留
    #print(s1)
    a = s1.pop(i)     #pop数据
    s2 = s1.copy()    #s1的备份：拿了数据以后要在各个位置插入，所有pop后的s1要保留
    #print(a)
    for j in range(l):#按照原来s0 的位置信息在各个位置插入刚刚pop出来的a
        s2.insert(j,a)
        #print(s1)
        s3.append(s2) #生成新的t并加入到元素为t的s3中
        s2 = s1.copy()#初始化s2
        j += 1
        
#2.去除重复的t及原始s0后得到s4

s4 = []               
for i in s3:
    if not i in s4:  #if not (i in s4 or i == s0):   也可以用并集的互补集表示
        if i != s0 : # and i[0] == '(' and i[len(s0)-1] != '('这里判不判断首位是不是‘(’并不重要，
       #毕竟后面也有判断按顺序读取s4【m】元素时，左括号数量是否大于右括号数量，一旦第一个是右括号，
       #元素s4【m】就不合法了
            s4.append(i)
#print(s3,len(s3))
#print(s4,len(s4))

#3.判断s4中t的合法性并计算s4中合法t的个数

for m in range(len(s4)):   #遍历s4中的各个t
    n0 = 0                 #参数初始化
    n1 = 0
    for n in range(len(s4[m])): #遍历单个t的各个元素时，判断左括号是否多于右括号，一旦左括号少于右括号，
        if s4[m][n] == '(':     #就是不合格括号序列， k1（作为flag参数）减一，
            n0 += 1
        else:
            n1 += 1
        if n0 < n1 :
            k1 -= 1
            break
    k1 += 1                     #给s4中的每个t都加1，在遇到不合法序列时减一，
print(k1)                       #其实这个加1可以省略，直接拿len（s4）来减就好了