If a is legal, (a), {a}, [a] are legal;
If a and b are both legal, ab is legal.
You are given a string S with length of n. Assume that Si(1 <= i <= n) is the i-th character of S. Your task is to find out whether there is a k(1 <= k <= n) that SkSk+1Sk+2…SnS1S2…Sk-1 is legal.
Input
There are several test cases. The first line contains an integer N. Then N test cases follows. In each test case, there is an only line that contains S. The length of S will not be larger than 1000. There are only (, ), {, }, [, ] in S.
Output
For each test case, output a single line “YES” (without quotation marks) if there is such a k, or “NO” (without quotation marks) otherwise.
Sample Input
3
}()[]{
}([)]{
()][
Sample Output
YES
NO
YES
! /usr/bin/env python
import string, sys
def exchange_str(str, i):
str1 = str[0:i]
str2 = str[i:]
return str2+str1
def is_legal(str):
if(len(str)==0):
return 1
if(len(str)==1):
return 0
if(str[0]=='('):
i = string.find(str, ")")
if(i==-1):
return 0
elif(i==len(str)-1):
return is_legal(str[1:len(str)-1])
else:
return is_legal(str[0:i+1]) and is_legal(str[i+1:len(str)])
if(str[0]=='['):
i = string.find(str, "]")
if(i==-1):
return 0
elif(i==len(str)-1):
return is_legal(str[1:len(str)-1])
else:
return is_legal(str[0:i+1]) and is_legal(str[i+1:len(str)])
if(str[0]=='{'):
i = string.find(str, "}")
if(i==-1):
return 0
elif(i==len(str)-1):
return is_legal(str[1:len(str)-1])
else:
return is_legal(str[0:i+1]) and is_legal(str[i+1:len(str)])
n = string.atoi(sys.stdin.readline())
while(n!=0):
str = sys.stdin.readline()
str = str[0:len(str)-1]
tmp = “”
legal = 0;
for i in range(0, len(str)):
tmp = exchange_str(str, i)
#print "==>"+tmp+"n"
if(is_legal(tmp)):
legal = 1
break
if(legal==1):
print "YES"
else:
print "NO"
n-=1
