#! /usr/bin/env python

# filterSatStrFromListOfStr.py
# P.Clote

# Program takes a list of secondary structures and
# outputs only those that are saturate. Used in conjunction
# with program which generates ALL secondary structures (homopolymer)
# of lengths <= n.


import sys,os

def isSat(secStr): #uses THETA=1
  s = ''; n = 0; D = {}
  #create data structure to test if structure is saturated
  for i in range(len(secStr)):
    if secStr[i]=='(':
      n += 1
    elif secStr[i]==')':
      n -= 1
    else:
      if n not in D.keys():
        D[n]=[ i ]
      else:
        D[n].append( i )
  #sort keys of D, and sort values i in D[k]
  keys = D.keys()
  keys.sort()
  for k in keys:
    #secStr not sat, if D[k] has > 2 elements, or 2 non-adjacent elements
    D[k].sort()
    L = D[k]
    if L[-1]-L[0]>1:
      return 0
  return 1
   
def main(filename):
  file = open(filename)
  line = file.readline()
  while line:
    if line[0]=='>':
      print line.strip()
    else:
      secStr = line.strip()
      if isSat(secStr): 
        print secStr
    line = file.readline()
  file.close()

if __name__ == '__main__':
  if len(sys.argv) < 2:
    print "Usage: %s filename" % sys.argv[0]
    sys.exit(1)
  filename = sys.argv[1]
  main(filename)