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:
- At any point, the number of
)(close) should be less than the number of((open) + number of:((frown) - 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)
