facebook-2013-qual-Parenthesis

import sys

def parse(S, begin_pos, smiley, paren_stack = 0):

    if paren_stack < 0:
        return False

    L = len(S)

    for cur_pos in range(begin_pos, L):
        ch = S[cur_pos]

        if ch == "(":
            balanced_smiley = False
            if S[cur_pos - 1] == ':':
                balanced_smiley = parse(S, cur_pos+1, True, paren_stack)

            balanced_nosmiley = parse(S, cur_pos+1, False, paren_stack+1)
            ret = balanced_smiley or balanced_nosmiley

            return ret

        elif ch==")":
            balanced_smiley = False
            if S[cur_pos - 1] == ':':
                balanced_smiley = parse(S, cur_pos+1, True, paren_stack)
            balanced_nosmiley = parse(S, cur_pos+1, False, paren_stack-1)
            ret = balanced_smiley or balanced_nosmiley

            return ret

    ret = paren_stack == 0

    return ret

fp = sys.stdin if len(sys.argv)<2 else open(sys.argv[1])

M = int(fp.readline())

for i in range(M):
    s = fp.readline().replace("\n",'')

    #print s
    print "Case #%d: %s" % (i+1, "YES" if parse(s, 0, False) else "NO")