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
        else // 3
                return 0;

            char expected = *it == '}' ? '{': *it == ']' ? '[' : '(';
            if( == expected)
                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