balancedSmileys.py

def balancedSmileys(string):
    def f(string,string_len,i,count):
        while i < string_len:
            w = string[i]
            if w == '(':
                # keep track of how many left brackets we have seen
                count += 1
            elif w == ')':
                # decrement "stack"
                count -= 1
                if count < 0:
                    # unbalanced, too many right brackets
                    return False
            elif w == ':' and i < (string_len - 1) and (string[i+1] == '(' or string[i+1] == ')'):
                # next pattern is ':' followed by '(' or ')'
                # recurive call to f 'skipping' both characters
                if f(string,string_len,i+2,count):
                    # if recursive call returns TRUE then pattern was a smiley/sad face
                    # parsing is complete.
                    return True
                # else string was not balanced. Continue and parse ':' as a colon
            i += 1
        # end of string, if count == 0 then string was balanced else too many left brackets
        return (count == 0)
    return f(string,len(string),0,0)