QualificationRound No.2 Balanced Smileys

2_BalancedSmileys.py

import sys
import re
from string import ascii_lowercase

ascii_lowercase = ascii_lowercase + " :"

def evaluate(string):
    """
    >>> evaluate(":((")
    False
    >>> evaluate("i am sick today (:()")
    True
    >>> evaluate("(:)")
    True
    >>> evaluate("hacker cup: started :):)")
    True
    >>> evaluate(")(")
    False
    >>> evaluate(":)(:)(:)))")
    True
    >>> evaluate("(:))(:))")
    True
    >>> evaluate("(((aaaaa:)))")
    True
    >>> evaluate("(((:)aaaaa:)))")
    True
    >>> evaluate("lll :(:):(:):(:):(:)")
    True
    >>> evaluate("#()")
    False
    >>> evaluate("")
    True
    >>> evaluate("()(")
    False
    """
    level = 0
    open_magic = 0
    close_magic = 0
    i = 0
    stop = len(string)
    while(i < stop):
        if string[i:i+2] == ":(":
            open_magic += 1
            i += 2
        elif string[i:i+2] == ":)":
            close_magic += 1
            i += 2
        elif string[i] == '(':
            level += 1
            i += 1
        elif string[i] == ')':
            if level == 0:
                if open_magic > 0:
                    open_magic -= 1
                else:
                    return False
            else:
                level -= 1
            i += 1
        elif string[i] in ascii_lowercase:
            i += 1
        else:
            return False
    if level - close_magic <= 0:
        return True
    else:
        return False

def main():
    m = int(sys.stdin.readline().rstrip())
    for i in xrange(m):
        string = sys.stdin.readline().rstrip()
        print("Case #{0}: {1:s}".format(i+1,
            'YES' if evaluate(string) else 'NO'))

def _test():
    import doctest
    doctest.testmod()

if __name__ == "__main__":
    if len(sys.argv) > 1:
        if sys.argv[1] == "test":
            _test()
    else:
        main()