Balanced smileys check algorithm (part 4)

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. 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)
2. 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 > 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 > 0 and source[i-1] == ':':
                smile += 1
            else:
                right += 1
        elif source[i] == '(':
            if i > 0 and source[i-1] == ":":
                frown += 1
            else:
                left += 1
                if right + smile < 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)

Answer 1

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 > 0:
                  count -= 1
              # if needed pair with an optional parens
              elif opt_open > 0:
                  opt_open -= 1
              else:
                  return False
  
          if opt_close > count:
              opt_close = count
  
          has_eyes = (char == ':')
      return count <= opt_close
  

Answer 2

let's make this really simple ... since you're only interested in whether the expression is valid and don't want any further information, it's irrelevant whether you "destroy" the input. Consider using something like the following:

import re

def check_balance(source):
    raw_braces = re.sub("[^()]*|:[()]", "")

this removes smiles, frowns and everything irrelevant from the input. Checking for balanced parentheses becomes a triviality now:

braces = 0
for i in raw_braces:
    if i == '(':
        braces += 1
    else if i == ')':
        braces -= 1
        if braces < 0:
            return False
return braces == 0