Regular bracket sequences consist of opening and closing brackets of one or more types, with each opening bracket having a closing bracket, and (in the case of multiple types) their types do not overlap.
Correct SP:
( ( ) ) ( ) ( )
{ } [ ( ) ] ( )
{ [ ( { } ) ] }
Invalid SP:
) ) ( ( ) ) ( (
{ [ ( ] ) }
( ( ] }
To check if a bracket sequence of brackets is of the same type, just check the balance.
That is, we start a variable equal to zero (balance). Then we run through the string (if you don't know how to do this - RUN, STUPID!), increasing the balance when it meets the opening bracket and decreasing it when it meets the closing one. If at any stage the balance becomes negative or at the end it is not equal to zero, then the sequence is wrong.
|
In the case of the presence of brackets of several types, everything becomes a little more complicated. We create a stack to act as that balance variable. This is necessary because parentheses cannot overlap. When we walk through a line and encounter an opening parenthesis, we push it onto the stack. When we encounter a closing brace, we try to pop the opening brace of that type off the stack. If a brace of a different type is on the stack, the sequence is invalid. If the stack is non-empty at the end, the sequence is also invalid.
|
The generation of correct bracket sequences follows directly from the way the check is done - we just need to add new brackets without violating correctness. This is done by recursive iteration. If you don't know him - BE... ah, no, you can try to understand by reading further. Here is a code sample for one type of brackets:
#include <vector>
#include <iostream>
using namespace std;
int n; // Half length
vector<char> ans; // Our answer
void rec(int balance) {
if (ans.size() == 2 * n) { // If it does, then we're done < /span>
for (int i = 0; i < 2 * n; i++)
cout << ans[i] << " ";
cout << "\n";
}
if (ans.size() + balance + 2 <= n * 2) { // Check, we'll make it do we close the new opening brace
// Now watch your hands: we don't need to make a separate vector for each sequence
ans.push_back('(');
rec(balance + 1);
ans.pop_back(); // To understand this, you need to be aware of recursion. First, we add a parenthesis to the vector, and then we execute all this code again.
// That is, add a parenthesis again, if we can.
// And this will happen until we start to leave the recursion - that is, until we reach the desired length.
// Then the brackets will start to be removed. If you understand this - I congratulate you, you are awesome.
}
if (balance > 0) { // If we can close a bracket, we close it.
ans.push_back(')');
rec(balance - 1);
ans.pop_back();
}
}
int main()
{
cin>> n;
rec(0);
return 0;
}
And now the time of difficulties - you will have to write the algorithm for several types of brackets YOURSELF! Muahahahahahahahahahahahah!
|