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

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)

• It's nice to see that after ~100 questions you've got to put the right tags :) Keep it up ! (@200_success will be proud) Commented Feb 9, 2017 at 20:43
• @Dex'ter, I am asking 200_success if I can (have permission) add new tags. haha. :) Commented Feb 9, 2017 at 20:49

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

• Thanks user650881, nice catch for the bug! Mark your reply as answer. Applied your advice, and make a new post here => codereview.stackexchange.com/questions/155072/…, if you have any advice, it will be great. Commented Feb 11, 2017 at 5:31
• BTW, like your option for using pre and points in clarity part. I reserve my option to use them in my new post, I think they are not major issues, comparing to other major great points by you. :) Commented Feb 11, 2017 at 5:33