Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

On Facebook HackerCup 2013, they asked the following question:

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.

Balancing parentheses is talked about in a lot of places. E.g. (()) vs ()(). You can count

  • '(' = +1
  • ')' = -1

Then you have to make sure your sum never falls below 0.

In this question they consider :) and :( as balanced and I wonder how much it changes things. One solution says that you can replace r'[^a-z:() ], '', ':)' -> '}' and ':(' -> '{'.

While I agree with the first sub, why are the last two substitutions valid?

share|improve this question
    
You have to read the subroutine is_balanced (at least the comment of it) to understand how that algorithm works. –  Tsuyoshi Ito Jan 29 '13 at 22:53

1 Answer 1

The solution is correct because the "}" and "{" symbols are considered "optional" parentheses.

(:):):(:::) → (}}{}

The left one is an example of an input string, the right is the preprocessed version of it. If you read the algorithm, you see that they keep two values,

min_level, max_level = (0, 0).

Reading the actual solution should convince you.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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