Les séquences de parenthèses régulières consistent en des parenthèses ouvrantes et fermantes d'un ou plusieurs types, chaque parenthèse ouvrante ayant une parenthèse fermante, et (dans le cas de plusieurs types) leurs types ne se chevauchent pas.
SP correct :
( ( ) ) ( ) ( )
{ } [ ( ) ] ( )
{ [ ( { } ) ] }
SP non valide :
) ) ( ( ) ) ( (
{ [ ( ] ) }
( ( ] }
Pour vérifier si une séquence de parenthèses est du même type, il suffit de vérifier l'équilibre.
Autrement dit, nous commençons une variable égale à zéro (solde). Ensuite, nous parcourons la chaîne (si vous ne savez pas comment faire - COUREZ, STUPIDE !), En augmentant l'équilibre lorsqu'il rencontre le crochet d'ouverture et en le diminuant lorsqu'il rencontre celui de fermeture. Si à n'importe quel moment le solde devient négatif ou à la fin il n'est pas égal à zéro, alors la séquence est fausse.
|
Dans le cas de la présence de supports de plusieurs types, tout devient un peu plus compliqué. Nous créons une pile pour agir comme cette variable d'équilibre. Ceci est nécessaire car les parenthèses ne peuvent pas se chevaucher. Lorsque nous parcourons une ligne et rencontrons une parenthèse ouvrante, nous la poussons sur la pile. Lorsque nous rencontrons une accolade fermante, nous essayons de retirer l'accolade ouvrante de ce type de la pile. Si une accolade d'un type différent se trouve sur la pile, la séquence n'est pas valide. Si la pile n'est pas vide à la fin, la séquence est également invalide.
|
La génération de séquences de parenthèses correctes découle directement de la façon dont la vérification est effectuée - nous avons juste besoin d'ajouter de nouvelles parenthèses sans violer l'exactitude. Cela se fait par itération récursive. Si vous ne le connaissez pas - BE... ah, non, vous pouvez essayer de comprendre en lisant plus loin. Voici un exemple de code pour un type de parenthèse :
#include <vecteur>
#include <iostream>
en utilisant espace de noms std ;
entier n ; // Demi-longueur
vecteur<char> ; répondez ; // Notre réponse
void rec(int balance) {
if (ans.size() == 2 * n) { // Si c'est le cas, alors nous sommes fait < /span>
pour (int i = 0 ; i < 2 * n ; i++)
cout << ans[i] << " ";
cout << "\n" ;
}
if (ans.size() + balance + 2 <= n * 2) { // Vérifie, nous allons faire en sorte que nous fermions la nouvelle accolade ouvrante
// Maintenant faites attention à vos mains : nous n'avons pas besoin de créer un vecteur séparé pour chaque séquence
ans.push_back('(');
rec(solde + 1);
ans.pop_back(); // Pour comprendre cela, vous devez être conscient de la récursivité. Tout d'abord, nous ajoutons une parenthèse au vecteur, puis nous exécutons à nouveau tout ce code.
// Autrement dit, ajoutez à nouveau une parenthèse, si nous le pouvons.
// Et cela se produira jusqu'à ce que nous commencions à quitter la récursivité - c'est-à-dire jusqu'à ce que nous atteignions la longueur souhaitée.
// Ensuite, les crochets commenceront à être supprimés. Si vous comprenez cela - je vous félicite, vous êtes génial.
}
if (balance > 0) { // Si nous pouvons fermer une parenthèse, nous la fermons.
ans.push_back(')');
rec(solde - 1);
ans.pop_back();
}
}
int main()
{
cin>> n;
rec(0);
retour 0 ;
}
Et maintenant, le temps des difficultés - vous devrez écrire vous-même l'algorithme pour plusieurs types de parenthèses ! Muahahahahahahahahahahahah !
|