Imprime toutes les chaînes de parenthèses équilibrées formées en remplaçant le caractère générique "?"

Parenthèses équilibrées signifie que si nous avons une chaîne de parenthèses, alors chaque parenthèse ouverte a une parenthèse fermante correspondante et les paires de parenthèses sont correctement imbriquées. La taille de la chaîne doit être un nombre pair. Dans ce problème, nous recevons une chaîne de crochets contenant le caractère « ? » et notre tâche est de former toutes les chaînes de crochets équilibrées possibles en remplaçant « ? » par le crochet approprié. Dans notre chaîne donnée, seules les parenthèses '(' et ')' sont utilisées.

Exemple Exemple

Input 1: str = “()(?)?”
Output 1: ()(()) 

La traduction chinoise de

Explication

est :

Explication

Seule une chaîne équilibrée peut être formée en remplaçant '?'.

Input 2: str = “??????”

Output 2: ((()))
(()())
(())()
()(())
()()()

La traduction chinoise de

Explication

est :

Explication

Il existe deux manières possibles de former une corde équilibrée.

• Une solution consiste à remplacer les indices 0, 1 et 2 par une parenthèse ouverte et les autres indices par une parenthèse fermée.

• La deuxième méthode consiste à remplacer les indices 0, 1 et 3 par une parenthèse ouverte et les autres indices par une parenthèse fermée.

• La troisième méthode consiste à remplacer les indices 0, 1 et 4 par des parenthèses ouvertes et les autres indices par des parenthèses fermées.

• La quatrième méthode consiste à remplacer les positions à l'index 0, 2 et 3 par une parenthèse ouverte et les autres positions de l'index par une parenthèse fermée.

• La dernière façon est de remplacer les indices 0, 2 et 4 par des parenthèses ouvertes et les autres indices par des parenthèses fermées.

Méthode

Nous avons vu l'exemple de la chaîne donnée ci-dessus, passons à l'étape suivante -

Nous pouvons utiliser la méthode du backtracking pour résoudre ce problème.

Parlons de cette méthode ci-dessous -

• Tout d'abord, nous allons initialiser une fonction appelée 'create' pour créer toutes les chaînes possibles après avoir remplacé '?' par des crochets, avec les paramètres str et index = 0.

• Dans cette fonction,

−> Tout d’abord, nous définissons les conditions de base. Si nous atteignons la fin de la chaîne, alors nous devons passer la chaîne à la fonction "check" pour vérifier que la chaîne est équilibrée. S'il est équilibré, imprimez la chaîne.

−>Si le caractère actuel de la chaîne est « ? »,

Tout d'abord, remplacez-le par un crochet ouvert et appelez la même fonction pour vérifier si la fin de la chaîne est atteinte.

Deuxièmement, remplacez-le par le crochet fermant et appelez à nouveau la même fonction pour vérifier si nous avons atteint la fin de la chaîne.

Enfin, nous revenons en arrière sur la chaîne et attribuons le caractère actuel à « ? »

−> Sinon, si le caractère actuel de la chaîne est un crochet, passez à l'index suivant en appelant la même fonction.

• Initialisez la fonction 'check' pour vérifier si la chaîne est équilibrée.

−> Dans cette fonction, nous initialisons la pile puis vérifions

−> Si le premier caractère de la chaîne est un crochet fermant, renvoie false

−> Si la parenthèse actuelle est fermée, il existe deux situations : si la pile est vide, false est renvoyé car il n'y a pas de parenthèse ouverte correspondante. Sinon, retirez le support ouvert correspondant de la pile.

−> Enfin, nous vérifions si la pile est vide. Si elle est vide, cela signifie que la chaîne est équilibrée et renvoie vrai. Sinon, il reste quelques crochets, ce qui signifie que la chaîne est déséquilibrée et renvoie faux.

La traduction chinoise de

Exemple

est :

Exemple

Ce qui suit est le code C++ utilisé pour la méthode de retour en arrière ci-dessus afin d'obtenir toutes les chaînes équilibrées

#include <bits/stdc++.h>
using namespace std; 
// Function 'check' to verify whether the string is balanced or not
bool check(string str){
   stack<char> S; // created stack 
   
// If the first character of the string is a close bracket, then return false
   if (str[0] == ')') {
      return false;
   } 
   
   // Traverse the string using for loop 
   for (int i = 0; i < str.size(); i++) { 
   
      // If the current character is an open bracket, then push it into the stack
      if (str[i] == '(') { 
         S.push('(');
      } 
      
      // If the current character is a close bracket
      else { 
      
         // If the stack is empty, there is no corresponding open bracket return false
         if (S.empty()){
            return false;
         }
         
         // Else pop the corresponding opening bracket from the stack
         else
            S.pop();
      }
   } 
   
   // If the stack is empty, return true
   if (S.empty()){
      return true;
   }
   else {
      return false;
   }
} 

// Function 'create' to create all possible bracket strings
void create(string str, int i){ 

   // If reached the end of the string
   if (i == str.size()) { 
   
      // passed 'str' to the 'check' function to verify whether the string is balanced or not
      if (check(str)) { 
      
         // If it is a balanced string
         cout<< str << endl; // print the string
      }
      return; 
   } 
   
   // If the current character of the string is '?'
   if (str[i] == '?') { 
      str[i] = '('; // replace ? with (
      create(str, i + 1); // continue to next character 
      str[i] = ')'; // replace ? with )
      create(str, i + 1); // continue to next character 
      
      // backtrack
      str[i] = '?';
   }
   
   // If the current character is bracketed then move to the next index
   else {
      create(str, i + 1);
   }
} 
int main(){
   string str = "??????"; //given string 
   
   // Call the function
   create (str, 0);
   return 0;
}

Sortie

((()))
(()())
(())()
()(())
()()()

Complexité temporelle et complexité spatiale

La complexité temporelle du code ci-dessus est O(N*(2^N)) car nous devons revenir en arrière sur la chaîne.

La complexité spatiale du code ci-dessus est O(N) car nous stockons les crochets sur la pile.

Où N est la taille de la chaîne.

Conclusion

Dans ce didacticiel, nous avons implémenté un programme qui imprime toutes les chaînes de parenthèses équilibrées pouvant être formées en remplaçant le caractère générique « ? ». Nous avons mis en place une méthode de backtracking. La complexité temporelle est O(N*(2^N) et la complexité spatiale est O(N). Où N est la taille de la chaîne.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!