Pages

Codility Nesting

Given a string that contains only open and close round brackets, check if they are all properly nested.

This is "painless" codility problem in the Stacks and Queues, is very close to its brother Brackets that we have just seen. Only, it is even simpler than that.

Well, it is painlessly easy if we take the right path, and consider it, as suggested by the section in which it is included, as a stack-related problem. If you miss this detail, you could find yourself in a bit more complicated territory. Have a look at this other post if you want to read some more stuff in that direction.

Otherwise, you could have a look at my C++11 solution:
int solution(std::string& input)
{
    int count = 0; // 1
    for(auto it = input.begin(); it != input.end(); ++it) // 2
    {
        if(*it == '(')
            ++count;
        if(*it == ')') // 3
        {
            if(!count)
                return 0;
            --count;
        }
    }
    return count == 0 ? 1 : 0; // 4
}
1. In this simple case, instead of using a proper stack, we can emulate it by using an integer. Have a look at Brackets to see a slight different version of this problem where a real stack makes more sense.
2. Loop on all the input elements, when we find an open bracket the counter is increased, as if we put it in a stack.
3. When a close bracket is found, we should pop the stack (i.e. decrease the counter). Still, we have to be careful, and ensure that the stack is not empty, that would mean no matching open bracket was previously seen.
4. I could have relied on the C++ automatic conversion from boolean type to integer, and avoid the use of the ternary operator. In any case, the meaning of this line is, only if the stack is empty (actually, the counter is zero) the function returns success.

No comments:

Post a Comment