Balanced smileys check algorithm (part 4) 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:


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 &gt; 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 &gt; 0 and source[i-1] == ':':
                smile += 1
            else:
                right += 1
        elif source[i] == '(':
            if i &gt; 0 and source[i-1] == ":":
                frown += 1
            else:
                left += 1
                if right + smile &lt; left:
                    return False
    return True

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

I suggest you add a test to verify(':):)(():(:(', False).  Perhaps your counters need to be reset?

Algorithm

The great thing about your algorithm is its simplicity.  However the algorithm now requires scanning the loop twice. The problem can be evaluated in a single pass with a different strategy, should you wish to consider performance.

Coding

Consider whether every line in your algorithm is actually relevant to the result.  Specifically, if you don't use smile in the first loop or frown in the second loop, why count them?

Beyond that and the stylistic comments I made previously, you might sit back in your chair and scan your solution.  Where the meaning, intent and motivation are unclear you might consider augmenting it by variable name selection and with comments.

Alternate Strategy

As an example of an alternate strategy that only requires scanning once, you might 


keep a count of unpaired parens, opt_open, opt_close
borrow from opt_open as needed to pair with excess close parens
ensure opt_close never exceeds unpaired parens count since those are out of scope
ensure final unpaired parens count does not exceed opt_close

def check_balance(src):
    opt_open = opt_close = 0
    count = 0
    has_eyes = False

    for char in src:
        if char == '(':
            if has_eyes:
                opt_open += 1
            else:
                count += 1

        elif char == ')':
            if has_eyes:
                opt_close += 1
            elif count &gt; 0:
                count -= 1
            # if needed pair with an optional parens
            elif opt_open &gt; 0:
                opt_open -= 1
            else:
                return False

        if opt_close &gt; count:
            opt_close = count

        has_eyes = (char == ':')
    return count &lt;= opt_close