2
\$\begingroup\$

This is a follow-up for here.

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

I'm wondering if 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
    frown = 0
    smile = 0
    for i,c in enumerate(source):
        if c == '(':
            left += 1
            if i > 0 and source[i-1] == ':': # :(
                left -= 1
                frown += 1
        elif c == ')':
            right += 1
            if i > 0 and source[i-1] == ':': # :)
                right -= 1
                smile += 1
                if left + frown < right:
                    return False
    if left > right + smile:
        return False
    return True
if __name__ == "__main__":
    raw_smile_string = 'abc(b:)cdef(:()'
    print check_balance(raw_smile_string)
\$\endgroup\$
4
  • 1
    \$\begingroup\$ You've asked a lot of questions on Code Review. Please do a better job picking tags for your questions. In this case, since you're asking a follow-up question, it should have been obvious which tags to use. \$\endgroup\$ Feb 8 '17 at 18:48
  • \$\begingroup\$ @200_success, would love to follow your advice, for follow-up question, what is the suggested tag? \$\endgroup\$
    – Lin Ma
    Feb 9 '17 at 7:00
  • 1
    \$\begingroup\$ Well, I added balanced-delimiters to the previous question, so obviously it should apply to this question too. \$\endgroup\$ Feb 9 '17 at 7:02
  • \$\begingroup\$ @200_success, for sure, thanks. Is it possible I can add some tags? So that if I post different version of code, I can refer old post by tag (from the new version of code post)? \$\endgroup\$
    – Lin Ma
    Feb 9 '17 at 20:34
3
\$\begingroup\$
  • In the verbal description of the algorithm, "should be less than" implies "not equal", which would not be correct. A wording such as "must be at most" would be totally clear.
  • Your code has a bug because you are not quite following rule 1. The rule says "at any point...", but you only check the rule after a smiley. You miss the case when a lone ) breaks the rule.
  • Instead of canceling += 1 with -= 1 here...

    left += 1
    if i > 0 and source[i-1] == ':': # :(
        left -= 1
        frown += 1
    

    ... it would be clearer to use else:

    if i > 0 and source[i-1] == ':': # :(
        frown += 1
    else:
        left += 1
    
  • Instead of if i > 0 and source[i-1] == ':' it would be simpler to remember the previous character in a variable:

     previous_char = None 
     for char in source:
         if char == 'c':
             if previous_char == ':':
         ...
         previous_char = char
    
\$\endgroup\$
4
  • 1
    \$\begingroup\$ instead of manually setting the previous character in a variable, it would be clearer to use the itertools' pairwise recipe \$\endgroup\$ Feb 9 '17 at 10:04
  • 1
    \$\begingroup\$ @MathiasEttinger Good idea, but then checking if the first character of the string is ( or ) would be a special case. \$\endgroup\$ Feb 9 '17 at 12:54
  • 1
    \$\begingroup\$ Not necessarily, you just need to adapt pairwise: a, b = tee(iterable); yield next(a), None; yield from zip(a, b). And you iterate over with for char, previous in …. \$\endgroup\$ Feb 9 '17 at 13:48
  • \$\begingroup\$ Thanks Janne, I post a new thread (codereview.stackexchange.com/questions/154783/…) to address your comments, if you have advice on that, it will be great. Mark your reply as answer. \$\endgroup\$
    – Lin Ma
    Feb 9 '17 at 20:38
3
\$\begingroup\$

Some notes:

  • Variable naming
    • Can be greatly improved by the use of an IDE like IDEA which supports trivial variable renaming.
    • Don't use single character variables, index and character (or even char) is much more readable than i and c.
    • It's not immediately obvious what any of the variables are.
  • You only have one test case. There should be test cases including and excluding each of the types of content of a message. If you get started with the simplest one you can even use TDD to get to a working but simple design.
  • Knowing the index of the unbalanced parenthesis would be nice.
  • Checking the number of parentheses is not enough, you have to whether they match up. For example, your algorithm fails (reports True when it shouldn't) on strings like )(.
  • The assignment calls for a recursive solution:

    A message has balanced parentheses if it consists of one of the following: […] An open parenthesis '(', followed by a message with balanced parentheses, followed by a close parenthesis ')'.

    This means that within each pair of parentheses there must be a valid message, meaning all the rules apply within them.

\$\endgroup\$
5
  • \$\begingroup\$ Hi l0b0, I have the same question from @JanneKarila, if you could help to clarify, it will be great. \$\endgroup\$
    – Lin Ma
    Feb 9 '17 at 7:01
  • \$\begingroup\$ Hi l0b0, are there any code logical bug (for logical, I mean my code returns wrong conclusion about True/False for balance or not) in my posted code? \$\endgroup\$
    – Lin Ma
    Feb 9 '17 at 7:01
  • 1
    \$\begingroup\$ I did post an example of input leading to the wrong conclusion. And which "same question" do you refer to? \$\endgroup\$
    – l0b0
    Feb 9 '17 at 8:39
  • \$\begingroup\$ Thanks l0b0, I think you mean the example of )(? \$\endgroup\$
    – Lin Ma
    Feb 9 '17 at 20:35
  • \$\begingroup\$ BTW l0b0, I post a new thread (codereview.stackexchange.com/questions/154783/…) to address your comments, if you have advice on that, it will be great. Vote up for all of your comments. \$\endgroup\$
    – Lin Ma
    Feb 9 '17 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.