Pages

Codility Brackets

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

This is a "painless" problem in the Stacks and Queues, practicing area, on the codility web site.

When I compared my current solution to the previous one that I developed when codility didn't support C++11, I found out only minimal differences.

Firstly I wrote a few test cases, a couple of them are given by codility in the problem definition, I merely implemented them for GoogleTest:
TEST(Brackets, Given1)
{
    std::string input { "{[()()]}" };
    ASSERT_EQ(1, solution(input));
}

TEST(Brackets, Given2)
{
    std::string input { "([)()]" };
    ASSERT_EQ(0, solution(input));
}

TEST(Brackets, Empty)
{
    std::string input { "" };
    ASSERT_EQ(1, solution(input));
}
And this is my latest implementation:
int solution(std::string& input)
{
    if(input.size() % 2) // 1
        return 0;

    std::stack<char> buffer; // 2

    for(auto it = input.begin(); it != input.end(); ++it) // 3
    {
        switch(*it) // 4
        {
        case '(': case '[': case '{':
            buffer.push(*it);
            continue;
        }

        if(buffer.empty()) // 5
            return 0;

        char prev = buffer.top(); // 6
        if((*it == ')' && prev == '(') || (*it == ']' && prev == '[') || (*it == '}' && prev == '{'))
            buffer.pop();
        else
            return 0;
    }

    return buffer.empty() ? 1 : 0; // 7
}
1. An odd numbers of brackets implies bad nesting.
2. I am going to push on a stack all the open brackets, popping them as soon as a close one is found.
3. Loop on all the input elements.
4. If the current character is an open bracket, in any supported flavor, push it on the stack.
5. Otherwise, if the buffer is empty the current element is a bad one. It could be an unexpected close bracket or a dirty character. In any case I return failure.
6. Check the current element on stack top. If it is a matching bracket, pop it and check the next input value.
7. After checking all the elements, we return success only if no open bracket is still lingering in the stack.

1 comment: