Calculez le nombre de paires qui doivent être supprimées pour que toutes les sous-séquences de brackets équilibrées soient vides

Le compilateur C traite les chaînes comme des tableaux de caractères, il est donc facile de supprimer des caractères d'une chaîne en fonction de leur position. Les première et dernière positions de la chaîne doivent être vérifiées pour la présence de parenthèses et doivent être supprimées. La chaîne peut être copiée dans une autre variable et affichée.

Il existe de nombreuses fonctions prédéfinies en C qui peuvent être utilisées efficacement pour manipuler des chaînes. En langage C, supprimer un caractère de la position de début ou de fin est facile à l’aide de fonctions.

Supprimez les crochets d'ouverture et de fermeture de la chaîne

Les crochets sont des caractères uniques qui font partie de la chaîne d'entrée et peuvent être supprimés de la chaîne en suivant la logique et l'algorithme indiqués ci-dessous

Le caractère est n'importe quelle touche alphanumérique que nous voyons sur le clavier et il est stocké dans la variable caractère en C.

() sont appelés parenthèses en c. Nous devons identifier ce caractère dans la chaîne saisie par l'utilisateur et le supprimer de la chaîne.

Un tableau est une variable qui possède de nombreux emplacements de stockage adressés par un seul nom et un numéro consécutif, alors qu'une chaîne est un tableau de caractères.

Il existe de nombreuses situations dans lesquelles nous devons supprimer les crochets des chaînes, par exemple lors de la résolution d'expressions régulières.

Grammaire

La fonction countRemoval accepte la chaîne str comme entrée et renvoie une valeur entière représentant le nombre de paires de suppression requises pour rendre vides toutes les sous-séquences de crochets équilibrés dans la chaîne. La fonction utilise la variable count pour suivre le nombre de suppressions requises, initialement défini sur 0. Il utilise également la variable Balance pour suivre l'équilibre entre le nombre de crochets ouvrants et fermants dans la chaîne. La fonction parcourt ensuite la longueur de la chaîne et vérifie le caractère à chaque index. Si le caractère est une parenthèse gauche, le solde est augmenté de 1, et s'il s'agit d'une parenthèse droite, le solde est décrémenté de 1. Si le solde devient négatif, cela signifie qu'il y a une tranche droite supplémentaire, que le nombre de retraits est plus 1 et que le solde est remis à 0. Après la boucle, le décompte est mis à jour pour inclure le solde restant divisé par 2 comme quantité de suppression requise pour rendre vides toutes les sous-séquences de support d'équilibrage dans la chaîne.

int countRemoval(string str) {
   int count = 0;
   int balance = 0;
   for (int i = 0; i < str.length(); i++) {
      if (str[i] == '(') {
         balance++;
      } else {
         balance--;
      }
      if (balance < 0) {
         count++;
         balance = 0;
      }
   }
   count += balance / 2;
   return count;
} 

Algorithme

• Étape 1 - Déclarez str1, str2, initialisés à null.

• Étape 2 - Déclarer les variables entières len,n,i

• Étape 3 - Accepter str1 depuis la console

• Étape 4 - Vérifiez si le premier caractère est (

• Étape 5 - si n = 1

• Étape 6 - Lorsque n

• Étape 7 - Vérifiez si le dernier caractère de str2 est ).

• Étape 8 - Si oui, remplacez-le par

• Étape 9

  - Imprimez str2 contenant la chaîne d'entrée moins le signe ().

Méthode

Méthode 1

- Récursion par force brute : Dans la première méthode, nous utilisons la récursivité par force brute pour trouver toutes les sous-séquences possibles et vérifier si elles sont équilibrées. Si la sous-séquence est équilibrée, nous supprimons une paire de parenthèses et comptons le nombre de paires de parenthèses supprimées. Nous calculons le nombre minimum de suppressions de paires requises pour vider la chaîne.

Méthode 2

- Programmation dynamique : La deuxième méthode utilise la programmation dynamique pour optimiser la solution. Nous pouvons utiliser une table DP 2D pour stocker le nombre minimum de suppressions requises pour une sous-chaîne de l'index "i" à "j". Nous parcourons la chaîne et remplissons la table DP en fonction des critères donnés. Méthode 1 Récursion violente

Code

Dans ce code, nous vérifions toutes les combinaisons possibles de sous-séquences, ce qui entraîne une complexité temporelle exponentielle. Pour des intrants plus importants, cette méthode peut ne pas être efficace.

#include <iostream>
#include <string>
using namespace std;

int countRemovalsRecursion(const string &s, int index, int open) {
   if (index == s.size()) {
      return open;
   }

   if (s[index] == '(') {
      return countRemovalsRecursion(s, index + 1, open + 1);
   } else if (open > 0) {
      return countRemovalsRecursion(s, index + 1, open - 1);
   } else {
      return 1 + countRemovalsRecursion(s, index + 1, open);
   }
}

int main() {
   string s = "(()())(";
   cout << "Input string: " << s << endl;
   cout << "Minimum removals (Brute Force Recursion): " << countRemovalsRecursion(s, 0, 0) << endl;
   return 0;
}

Sortie

Input string: (()())(
Minimum removals (Brute Force Recursion): 1

Méthode 2

Exemple

Cette solution de programmation dynamique calcule le nombre minimum de suppressions nécessaires pour vider toutes les sous-séquences de brackets équilibrés. Il parcourt la chaîne, met à jour une table DP unidimensionnelle avec le nombre de crochets gauches et renvoie la valeur DP finale comme montant minimum à supprimer.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int countRemovalsDP(const string &s) {
   int n = s.size();
   vector<int> dp(n + 1, 0);

   for (int i = 0; i < n; ++i) {
      if (s[i] == '(') {
         dp[i + 1] = dp[i] + 1;
      } else {
         dp[i + 1] = max(dp[i] - 1, 0);
      }
   }
   return dp[n];
}

int main() {
   string s = "(()())()";
   cout << "Input string: " << s << endl;
   cout << "Minimum removals (Dynamic Programming): " << countRemovalsDP(s) << endl;
   return 0;
}

Sortie

Input string: (()())()
Minimum removals (Dynamic Programming): 0

Conclusion

Concepts de base du langage C, tels que la différence entre les types de données caractère et chaîne, les délimiteurs de chaînes, comment initialiser les chaînes et les tableaux, le calcul de la position où le premier caractère du tableau est l'index 0 et le dernier caractère est utilisé dans le programme Doit être vide pour obtenir une sortie correcte.

La suppression des parenthèses dans les programmes est obtenue en implémentant des concepts simples et basiques de programmation C.

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!