5
\$\begingroup\$

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. 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 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)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ It's nice to see that after ~100 questions you've got to put the right tags :) Keep it up ! (@200_success will be proud) \$\endgroup\$ Feb 9 '17 at 20:43
  • \$\begingroup\$ @Dex'ter, I am asking 200_success if I can (have permission) add new tags. haha. :) \$\endgroup\$
    – Lin Ma
    Feb 9 '17 at 20:49
7
\$\begingroup\$

Correctness

I suggest you add a test case for :)(. It should be False, but is not.

Testability

Consider adding assert tests for ease of testing and evaluation. Perhaps something like

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)

Besides, if provided, it is easier to refactor and propose alternatives when providing feedback. :)

Clarity

A key part of the challenge is that smiles and frowns are optionally allowed to balance parens. This is an important not immediately obvious point that is worth documenting in the code.

Though somewhat minor for this simple example, I prefer not to repeatedly test for pre == ':' since ":" is the only character you care about. Instead I would opt for something like eyes_flag which can be set at the end of loop as eyes_flag = c == ':'.

Though the criteria may change after fixing the implementation, expressions like this

if left > right + smile:
    return False
return True

can be simplified to

return left <= right + smile

Naming

This is a matter of opinion, but for me smiley and frown require too much effort to map to open and close parens. I prefer calling them optional open parens (opt_open) and optional close parens (opt_close).

\$\endgroup\$
2
  • \$\begingroup\$ Thanks user650881, nice catch for the bug! Mark your reply as answer. Applied your advice, and make a new post here => codereview.stackexchange.com/questions/155072/…, if you have any advice, it will be great. \$\endgroup\$
    – Lin Ma
    Feb 11 '17 at 5:31
  • \$\begingroup\$ BTW, like your option for using pre and points in clarity part. I reserve my option to use them in my new post, I think they are not major issues, comparing to other major great points by you. :) \$\endgroup\$
    – Lin Ma
    Feb 11 '17 at 5:33

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.