This is a follow-up for here, for bug fixes and applied advice.ProblemYour friend John uses a lot of emoticons when you talk to him on  Messenger. In addition to being a person who likes to express himself  through emoticons, he hates unbalanced parenthesis so much that it  makes him go :(Sometimes he puts emoticons within parentheses, and you find it hard  to tell if a parenthesis really is a parenthesis or part of an  emoticon.A message has balanced parentheses if it consists of one of the  following:An empty string One or more of the following characters: 'a' to 'z', ' ' (a space) or ':' (a colon)An open parenthesis '(', followed by a message with balanced parentheses, followed by a close parenthesis ')'.A message with balanced parentheses followed by another message with balanced parentheses.A smiley face :) or a frowny face :(Write a program that determines if there is a way to interpret his message while leaving the parentheses balanced.I'm working on this balanced smileys checking algorithm, and my current solution is very naive, with just two rules:Do a forward scan, at any point, the number of ) (close) should be less than or equal to the number of ( (open) + number of :( (frown)Do a backward scan, at any point, the number of ( (open) should be less than or equal to the number of ) (close) and :) (smile)I'm wondering if there are any bugs in my checking logic. Any advice on algorithm time complexity improvement or code style advice is highly appreciated as well.def check_balance(source):    pre = ''    left = 0    right = 0    frown = 0 # :(    smile = 0 # :)    # forward scan    for c in source:        if c == ')':            if pre == ':':                smile += 1            else:                right += 1                if right > left + frown:                    return False        elif c == '(':            if pre == ':':                frown += 1            else:                left += 1        pre = c    # reverse scan    for i in range(len(source)-1, -1, -1):        if source[i] == ')':            if i > 0 and source[i-1] == ':':                smile += 1            else:                right += 1        elif source[i] == '(':            if i > 0 and source[i-1] == ::                frown += 1            else:                left += 1                if right + smile < left:                    return False    return Truedef verify(test_input, expected_result):    actual_result = check_balance(test_input)    assert actual_result == expected_result, {} expected {} failed.format(test_input, expected_result)    print(test_input, actual_result)if __name__ == __main__:    verify(':)(', False)    verify(':()', True)    verify('abc(b:)cdef(:()', True)    verify('a)', False)    verify(')(' , False)
Balanced smileys check algorithm (part 4)
python;algorithm;python 2.7;balanced delimiters