Balanced smileys check algorithm (part 3)

Question

This is a follow-up for here, for bug fixes and applied advice.

Problem

Your 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:

1. At any point, the number of ) (close) should be less than the number of ( (open) + number of :( (frown)
2. At the end, the number of ( (open) should be less than 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):
    left = 0
    right = 0
    smile = 0 # :)
    frown = 0 # :(
    pre = ''
    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
    if left > right + smile:
        return False
    return True

if __name__ == "__main__":
    raw_smile_string = 'abc(b:)cdef(:()' # true
    raw_smile_string = 'a)' # false
    raw_smile_string = ')('  # false
    print check_balance(raw_smile_string)

Answer 1

Correctness

I suggest you add a test case for :)(. It should be False, but is not.

Testability

Consider adding assert tests for ease of testing and evaluation. Perhaps something like

def 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)

Besides, if provided, it is easier to refactor and propose alternatives when providing feedback. :)

Clarity

A key part of the challenge is that smiles and frowns are optionally allowed to balance parens. This is an important not immediately obvious point that is worth documenting in the code.

Though somewhat minor for this simple example, I prefer not to repeatedly test for pre == ':' since ":" is the only character you care about. Instead I would opt for something like eyes_flag which can be set at the end of loop as eyes_flag = c == ':'.

Though the criteria may change after fixing the implementation, expressions like this

if left > right + smile:
    return False
return True

can be simplified to

return left <= right + smile

Naming

This is a matter of opinion, but for me smiley and frown require too much effort to map to open and close parens. I prefer calling them optional open parens (opt_open) and optional close parens (opt_close).