Balanced smileys check algorithm (part 2)

Question

This is a follow-up for here.

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 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
    frown = 0
    smile = 0
    for i,c in enumerate(source):
        if c == '(':
            left += 1
            if i > 0 and source[i-1] == ':': # :(
                left -= 1
                frown += 1
        elif c == ')':
            right += 1
            if i > 0 and source[i-1] == ':': # :)
                right -= 1
                smile += 1
                if left + frown < right:
                    return False
    if left > right + smile:
        return False
    return True
if __name__ == "__main__":
    raw_smile_string = 'abc(b:)cdef(:()'
    print check_balance(raw_smile_string)

Answer 1

• In the verbal description of the algorithm, "should be less than" implies "not equal", which would not be correct. A wording such as "must be at most" would be totally clear.
• Your code has a bug because you are not quite following rule 1. The rule says "at any point...", but you only check the rule after a smiley. You miss the case when a lone ) breaks the rule.

• Instead of canceling += 1 with -= 1 here...

  left += 1
  if i > 0 and source[i-1] == ':': # :(
      left -= 1
      frown += 1
  

  ... it would be clearer to use else:

  if i > 0 and source[i-1] == ':': # :(
      frown += 1
  else:
      left += 1
  

• Instead of if i > 0 and source[i-1] == ':' it would be simpler to remember the previous character in a variable:

   previous_char = None 
   for char in source:
       if char == 'c':
           if previous_char == ':':
       ...
       previous_char = char
  

Answer 2

Some notes:

• Variable naming
  • Can be greatly improved by the use of an IDE like IDEA which supports trivial variable renaming.
  • Don't use single character variables, index and character (or even char) is much more readable than i and c.
  • It's not immediately obvious what any of the variables are.
• You only have one test case. There should be test cases including and excluding each of the types of content of a message. If you get started with the simplest one you can even use TDD to get to a working but simple design.
• Knowing the index of the unbalanced parenthesis would be nice.
• Checking the number of parentheses is not enough, you have to whether they match up. For example, your algorithm fails (reports True when it shouldn't) on strings like )(.

• The assignment calls for a recursive solution:

  A message has balanced parentheses if it consists of one of the following: […] An open parenthesis '(', followed by a message with balanced parentheses, followed by a close parenthesis ')'.

  This means that within each pair of parentheses there must be a valid message, meaning all the rules apply within them.