Sequências de colchetes regulares consistem em colchetes de abertura e fechamento de um ou mais tipos, com cada colchete de abertura tendo um colchete de fechamento e (no caso de vários tipos) seus tipos não se sobrepõem.
SP correto:
( ( ) ) ( ) ( )
{ } [ ( ) ] ( )
{ [ ( { } ) ] }
SP inválido:
) ) ( ( ) ) ( (
{ [ ( ] ) }
( ( ] }
Para verificar se uma sequência de colchetes é do mesmo tipo, basta verificar o saldo.
Ou seja, iniciamos uma variável igual a zero (saldo). Em seguida, percorremos a corda (se você não sabe como fazer isso - CORRA, ESTÚPIDO!), Aumentando o equilíbrio quando encontra o colchete de abertura e diminuindo quando encontra o de fechamento. Se em algum estágio o saldo ficar negativo ou no final não for igual a zero, então a sequência está errada.
|
No caso da presença de colchetes de vários tipos, tudo fica um pouco mais complicado. Criamos uma pilha para atuar como essa variável de equilíbrio. Isso é necessário porque os parênteses não podem se sobrepor. Quando percorremos uma linha e encontramos um parêntese de abertura, nós o colocamos na pilha. Quando encontramos uma chave de fechamento, tentamos retirar a chave de abertura daquele tipo da pilha. Se uma chave de um tipo diferente estiver na pilha, a sequência é inválida. Se a pilha não estiver vazia no final, a sequência também é inválida.
|
A geração de sequências corretas de colchetes segue diretamente da forma como a verificação é feita - só precisamos adicionar novos colchetes sem violar a exatidão. Isso é feito por iteração recursiva. Se você não o conhece - BE... ah, não, você pode tentar entender lendo mais. Aqui está um exemplo de código para um tipo de colchetes:
#include <vetor>
#include <iostream>
usando namespace std;
int n; // Meio comprimento
vetor<char> resposta; // Nossa resposta
void rec(int saldo) {
if (ans.size() == 2 * n) { // Se sim, então estamos feito < /span>
para (int i = 0; i < 2 * n; i++)
cout << ans[i] << " ";
cout << "\n";
}
if (ans.size() + saldo + 2 <= n * 2) { // Verifique, nós vamos fazer isso, fechamos a nova chave de abertura
// Agora cuidado com as mãos: não precisamos fazer um vetor separado para cada sequência
ans.push_back('(');
rec(saldo + 1);
ans.pop_back(); // Para entender isso, você precisa estar ciente da recursão. Primeiro, adicionamos um parêntese ao vetor e, em seguida, executamos todo esse código novamente.
// Ou seja, adicione um parêntese novamente, se pudermos.
// E isso vai acontecer até começarmos a sair da recursão - ou seja, até atingirmos o comprimento desejado.
// Então os parênteses começarão a ser removidos. Se você entende isso - eu parabenizo você, você é incrível.
}
if (balance > 0) { // Se pudermos fechar um colchete, nós o fechamos.
ans.push_back(')');
rec(saldo - 1);
ans.pop_back();
}
}
int main()
{
cin>> n;
rec(0);
retorno 0;
}
E agora a hora das dificuldades - você mesmo terá que escrever o algoritmo para vários tipos de colchetes! Muahahahahahahahahahahaha!
|