Pages

Matching many types of brackets

We have a string in input that could be quite longish (200K). It contains just a bunch of open and close brackets, in three possible varieties, round, squared, curly. We want to check if they are properly nested.

I have already discussed a similar problem in the past. In that case the string contained just one type of open/close parenthesis, so the job was even simpler.

I found this version of the problem in the Codility train page, section Stacks and Queues, under the nickname Brackets.

There you could find a couple of test cases, that I write here in C++ for the GoogleTest framework:
int solution(const std::string& input);

TEST(Brac, Given1) // 1
{
    ASSERT_EQ(1, solution("{[()()]}"));
}

TEST(Brac, Given2) // 2
{
    ASSERT_EQ(0, solution("([)()]"));
}
1. This is an example of a correctly nested string.
2. This is not. In third position it is not expected a closing round bracket, since there is a pending squared one before.

The same considerations I made for the simpler version of this problem apply here. The only variation is that I have to use a proper stack to keep memory of the pending open brackets.

Here is my C++98 implementation:
int solution(const std::string& input)
{
    if(input.size() % 2) // 1
      return 0;

    std::stack buffer;

    for(std::string::const_iterator it = input.begin(); it != input.end(); ++it)
    {
        if(*it == '{' || *it == '[' || *it == '(') // 2
            buffer.push(*it);
        else // 3
        {
            if(buffer.empty())
                return 0;

            char expected = *it == '}' ? '{': *it == ']' ? '[' : '(';
            if(buffer.top() == expected)
                buffer.pop();
            else
                return 0;
        }
    }

    if(buffer.empty()) // 4
        return 1;
    return 0;
}
1. There is no need of doing any check further in case of an uneven number of brackets.
2. If the current character is an open bracket, I put it in the stack.
3. Otherwise (assuming the input source is reliable) I expect it is a closing bracket that should match with a corresponding open one. If the stack is empty, the input string is corrupted, otherwise I determine which kind of bracket I expect, compare it with the element at the top of the stack, and pop it (if matches) or return the "no good" value.
4. Check a last time the stack, it should be empty now, otherwise we have some open bracket that we failed to close.

No comments:

Post a Comment