CodeEval Balanced Smileys

This problem is part of the family of the ones asking to check if parentheses in a sentence are balanced. See for instance the simpler matching brackets one.

In this version, happy ':)' and sad ':(' smileys could be part of the the sentence, so that we have to think if a parentheses has to be considered in the balancing or skipped, being the representation of the mouth of the smiley.

I found it as CodeEval #84 problem, but it is a repost, originally coming from Facebook Hacker Cup 2013 Hackathon.

I came to a solution inferior to the one published by the Hacker Cup editors, so I just threw mine in the dustbin and I spent some time pondering on the other one, coming out with a slightly different variation. [By the way, I would suggest you to do the same. When you see a piece of code you don't fully understand, play around with it, adapt it to your style, make it yours.]

The base problem is pretty simple. We loop on each character in the string, any time we see an open bracket, we push it in a stack (or we emulate a push in a stack, using just a counter). When we see a close bracket, we pop from the stack the matching open bracket. In the end, the stack should be empty. If we try to pop when the stack is empty, the sentence is unbalanced.

Having to care to the smileys, we need a second (virtual) stack, where we push also the dubious open brackets, the one that could have a double interpretation.

Looking at the code should clarify the sense of this solution:

min_open = 0  # 1
max_open = 0  # 2
for i in range(len(msg)):  # 3
    if msg[i] == '(':  #4
        max_open += 1
        if i == 0 or msg[i-1] != ':':  # 5
            min_open += 1
    elif msg[i] == ')':  # 6
        if i == 0:
            return False
        min_open = min_open - 1 if min_open else 0
        if msg[i-1] != ':':  # 7
            if max_open == 0:
                return False
            max_open -= 1
return True if min_open == 0 else False  # 8

1. Emulate the first stack. It keep track of the "clean" open brackets only.
2. The second "dirty" stack, containing also the brackets that could be seen as mouth for a sad smiley.
3. Loop an all the character in the sentence.
4. Open bracket, push it to the "dirty" stack (i.e. increase the max_open counter), and ...
5. ... only if it couldn't be seen as the mouth of a smiley, push it to the "clean" stack (i.e. increase the min_open counter)
6. Close bracket, if we are at the beginning, the sentence is unbalanced. Otherwise, pop the matching open bracket from the "clean" stack. If it was already empty, the sentence could be unbalanced. Not sure, however, because it could be a happy smiley. So ...
7. If the bracket could be seen as the mouth of a happy smiley, the "dirty" stack empty means the sentence is unbalanced, otherwise, pop a bracket from it.
8. Completed the loop, the sentence is balanced only if the "clean" stack is empty.

The full python script is on GitHub.