Matching balanced and nested curly braces in input text

Question

I attended the quiz, I gave the code, but the autotest shows that one of the eight tests failed. I myself have tested my code many times, but everything went well. I can not find where the problem is.

The question is to develop an algorithm for checking the matching of brackets in a string.

1) Just consider the brackets () and square brackets [] , omit the ohter characters.
2) Each pair of brackets must correspond to each other. This means that （ matches ) , and [ matches ] .
3) Intercrossing is not allowed, for example: ([)] . There are two pairs of brackets, but they cross each other.

To solve the problem, my method is described as follows:

• Search for every char in the entire input line, index from 0 to str.size () - 1.
• Use two stacks to write the opening tag ( and [ , each type in one stack. When you encounter one of them, click its index in the corresponding stack.
• When closing the closing tag ) and ] we pop up the appropriate stack.
• Before appearing, check the top of the two stacks, the current stack should have a maximum index, otherwise this means that there is an unmatched opening tag with a different type, so intercrossing can be checked in this way.

My code is here:

 #include <iostream> #include <stack> using namespace std; int main() { string str; cin >> str; stack<int> s1, s2; int result = 0; for (int ix = 0, len = str.size(); ix < len; ix++) { if (str[ix] == '(') { s1.push(ix); } else if (str[ix] == '[') { s2.push(ix); } else if (str[ix] == ')') { if (s1.empty() || (!s2.empty() && s1.top() < s2.top())) { result = 1; break; } s1.pop(); } else if (str[ix] == ']') { if (s2.empty() || (!s1.empty() && s2.top() < s1.top())) { result = 1; break; } s2.pop(); } else { // do nothing } } if (!s1.empty() || !s2.empty()) { result = 1; } cout << result << endl; } 

As before, this issue can only be solved on the stack, so I changed my code and here is the version of one stack. [KEY POINT DOESN'T PASS TO BE BETTER BUT WHAT IS WRONG WITH MY CODE.]

 #include <iostream> #include <stack> using namespace std; int main() { string str; cin >> str; stack<char> s; const char *p = str.c_str(); int result = 0; while (*p != '\0') { if (*p == '(' || *p == '[') { s.push(*p); } else if (*p == ')') { if (s.empty() || s.top() != '(') { result = 1; break; } s.pop(); } else if (*p == ']') { if (s.empty() || s.top() != '[') { result = 1; break; } s.pop(); } else { // do nothing } p++; } if (!s.empty()) { result = 1; } cout << result << endl; } 

Answer 1

When using formatted input to read a std::string , only the first word is read: after skipping the leading whitespate, the line is read until the first space appears. As a result, the input ( ) should match, but std::cin >> str will only read ( . Thus, the input should look like this:

 if (std::getline(std::cin, str)) { // algorithm for matching parenthesis and brackets goes here } 

Using std::getline() still makes an assumption about how the input is presented, namely that it is on the same line. If the algorithm should handle all input from std::cin , I would use

 str.assign(std::istreambuf_iterator<char>(std::cin), std::istreambuf_iterator<char>()); 

Although I believe that the algorithm is unnecessarily complicated (the appearance of the brackets will be preserved on the stack), I also think that it should work, i.e. the only problem I discovered is the way I get input.