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::stack1. There is no need of doing any check further in case of an uneven number of brackets.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; }

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