Правильные скобочные последовательности состоят из открывающих и закрывающих скобок одного или нескольких типов, причём для каждой открывающей скобки есть закрывающая, и (в случае нескольких типов) их типы не перекрываются.
Правильные СП:
( ( ) ) ( ) ( )
{ } [ ( ) ] ( )
{ [ ( { } ) ] }
Неправильные СП:
) ) ( ( ) ) ( (
{ [ ( ] ) }
( ( ] }
Чтобы проверить, является ли скобочная последовательность из скобок одного типа, достаточно проверять баланс.
То есть мы заводим переменную, равную нулю (balance). Затем мы пробегаем по строке (если вы не умеете это делать - БЕГИТЕ, ГЛУПЦЫ!), увеличивая balance при встрече открывающей скобки и уменьшая - при закрывающей. Если на любом этапе баланс становится отрицательным или в конце он не равен нулю, значит, последовательность неправильная.
|
В случае наличия скобок нескольких типов всё становится чуть сложнее. Мы создаём стек, выполняющий роль той переменной balance. Это нужно, поскольку скобки не могут перекрываться. Проходя по строке и встречая открывающую скобку, мы кладём её в стек. Встречая закрывающую, мы пытаемся вынуть из стека открывающую скобку этого типа. Если на стеке лежит скобка другого типа, последовательность неправильная. Если в конце стек оказался непустым, последовательность также неправильная.
|
Генерация правильных скобочных последовательностей напрямую вытекает из способа проверки - нам просто нужно добавлять новые скобочки, не нарушая корректности. Делается это методом рекурсивного перебора. Если вы его не знаете - БЕ... а, нет, можете попытаться понять, читая дальше. Вот образец кода для одного типа скобок:
#include <vector>
#include <iostream>
using namespace std;
int n; // Половина длины
vector<char> ans; // Наш ответ
void rec(int balance) {
if (ans.size() == 2 * n) { // Если выполняется - значит, мы закончили
for (int i = 0; i < 2 * n; i++)
cout << ans[i] << " ";
cout << "\n";
}
if (ans.size() + balance + 2 <= n * 2) { // Проверяем, успеем ли мы закрыть новую открывающую скобку
// А теперь следите за руками: нам не нужно делать отдельный вектор для каждой последовательности
ans.push_back('(');
rec(balance + 1);
ans.pop_back(); // Чтобы это понять, нужно осознавать рекурсию. Вначале мы добавляем в вектор скобку, а потом выполняем весь этот код снова.
// То есть опять добавляем скобку, если можем.
// И так будет происходить, пока мы не начнём из рекурсии выходить - то есть, пока мы не дойдём до нужной длины.
// Тогда скобки начнут удаляться. Если вы это поняли - я вас поздравляю, вы классный(ая).
}
if (balance > 0) { // Если можем закрыть какую-то скобку - закрываем.
ans.push_back(')');
rec(balance - 1);
ans.pop_back();
}
}
int main()
{
cin >> n;
rec(0);
return 0;
}
А теперь время сложностей - алгоритм для нескольких типов скобок вам придётся писать САМИМ! Муахахахахахахахахахахахаха!
|