smileys.py

#!/usr/bin/env python
import re


def is_balanced(text):
    """Given text containing only braces ((, ), {, }), returns `True`
    if they can be balanced. Returns `False` otherwise.

    Curly braces ({ and }) are treated as optional.
    """
    min_level, max_level = (0, 0)
    for c in text:
        if c == '(':
            min_level += 1
            max_level += 1
        elif c == ')':
            min_level = max(min_level - 1, 0)
            max_level -= 1
            if max_level < 0:
                return False
        elif c == '{':
            max_level += 1
        elif c == '}':
            min_level = max(min_level - 1, 0)
    return min_level <= 0 <= max_level

    
def smileys(text):
    if re.search(r'[^a-z:() ]', text):
        # Correct string may contain only characters: 'a' to 'z',
        # ' ' (a space), ':' (a colon) and '(' ')' (parentheses)
        return False
        
    # Clean text
    text = text.replace(':)', '}')
    text = text.replace(':(', '{')
    text = re.sub(r'[a-z: ]', '', text)

    return is_balanced(text)


if __name__ == '__main__':
    import sys
    for j, line in enumerate(list(sys.stdin)[1:]):
        print "Case #{}: {}".format(j + 1, 'YES' if smileys(line[:-1]) else 'NO')