Balanced smileys check algorithm (part 3)

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:

• At any point, the number of ) (close) should be less than the number of ( (open) + number of :( (frown)

• 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

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

StackExchange Code Review Q#154949, answer score: 7