This is a continued discussion here (Balanced smileys check algorithm (part 2)), since new code (for bug fix and applied advice from previous post), I start a new thread.
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, just two rules
- At any point, number of
) (close) should be less than number of ( (open) + number of :( (frown);
- At the end, number of
( (open) should be less than number of ) (close) and :) (smile).
Wondering if any bugs in my checking logic above.
Any advice on algorithm time complexity improvement or code style advice is highly appreciated as well.
Source code in Python 2.7,
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)
