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
  

• user650881: My response had a bit of churn. I hope it didn't cause any confusion.
• Lin Ma: Thanks user650881, yes I do scan twice, is there any solution only scan once?

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

• user650881: Great approach to rethinking the strategy. Unfortunately the problem statement is not just parens balancing. When proceeded by a colon the parens can be used to balance or be ignored as needed. "(:()" and ":()" are both consider balanced. (Also your regex might be a bit hastily constructed. I'm not sure it actually implements your intent.)
• Lin Ma: Hi Vogel612, I think @user650881 is correct, if you have any great ideas for the original problem, appreciate for sharing.