Supprimez les crochets de la chaîne algébrique contenant les opérateurs + et - en utilisant C++

Étant donné une chaîne algébrique comme p-(q-r)-s, nous devons supprimer les crochets et convertir la chaîne en une chaîne avec le même résultat mathématique. Par conséquent, la chaîne p-(q-r)-s est convertie en p-q+r-s, donnant le même résultat mathématique. Pour y parvenir, nous pouvons utiliser la pile et savoir si le symbole à venir dans l'expression entre crochets doit être inversé.

• 0 signifie + ou pas de flip

• 1 signifie - ou retournez

Donc à chaque ouverture de parenthèse nous pousserons 0 ou 1 selon que le signe dans la parenthèse est retourné ou non. Lorsque nous voyons le crochet fermant, nous faisons éclater la pile.

Remarque - Nous ne considérons pas les chaînes commençant par des parenthèses. Il faut nettoyer ce type de chaîne. Par exemple, s="(p-(q+r))" doit être s="p-(q+r)". Dans ce cas, nous pouvons facilement exécuter une boucle de l'index 1 à la longueur -2 puis de 0 à la longueur -1.

Regardons quelques scénarios d'entrée

En supposant que l'entrée de la méthode est un certain nombre de types de données chaîne, dans la liste des résultats, nous obtenons l'expression sauf les crochets -

Input: (2×3)─(6─(4+5))
Result: 2×3–6+4+5

Supposons que la saisie de la méthode commence par des parenthèses, dans la liste des résultats, nous obtenons une expression sans parenthèses comme suit -

Input: (a+(b-c-d)-e)
Result: a-b+c+d+e

Remarque - Nous ne prenons pas en compte les chaînes commençant par des parenthèses dans le programme. Il faut nettoyer ce type de chaîne. Par exemple, s="(a+(b-c-d)-e)" doit être s="a+(b-c-d)-e". Dans ce cas, nous pouvons facilement exécuter une boucle de l'index 1 à la longueur -2 puis de 0 à la longueur -1.

Ici, nous pouvons utiliser une expression polynomiale incluant des parenthèses comme entrée, donc dans la liste résultante, nous obtenons une expression comme celle-ci -

Input: (p*p)-(p-q)
Result: p*p-p+q

Nous avons appliqué cela aux polynômes quadratiques, mais la méthode peut également être utilisée pour des expressions polynomiales d'ordre supérieur.

Exemple

Supposons que nous ayons trois chaînes S1, S2 et S3 avec les valeurs suivantes -

string s1 = "p-(-q+(-r+(s-t)))";
string s2 = "(p+q-r+t+u)";
string s3 = "(p+ (q-r-t)-u)";

Utilisons donc la méthode C++ pour supprimer les crochets de la chaîne ci-dessus contenant les opérateurs + et -. Voici un programme C++ pour le problème donné -

#include <iostream>
#include <stack>
using namespace std;
string solve(string s) {
   stack<int> sk;
   sk.push(0);
   string res = "";
   for(int i=0;i<s.size();i++) {
      if(s[i] == '(') {
         int temp = s[i-1] == '+' ? 0 : 1;
         if(sk.top() == 0) sk.push(temp);
         else sk.push(temp^1);
      } else if(s[i] == ')') {
         sk.pop();
      } else if(s[i] == '+' || s[i] == '-') {
         char op;
         if(sk.top() == 0) op = s[i];
         else op = (s[i]=='+' ? '-' : '+');
         if(res.size() != 0 && (res[res.size()-1]=='+' || res[res.size()- 1]=='-')) res[res.size()-1] = op;
         else res+=op;
      } else {
         res+=s[i];
      }
   }
   return res;
}
int main() {
   string s1 = "p-(-q+(-r+(s-t)))";
   string s2 = "(p+q-r+t+u)";
   string s3 = "(p+ (q-r-t)-u)";
   cout << solve(s1) << endl;
   cout << solve(s2) << endl;
   cout << solve(s3) << endl;
   return 0;
}

Sortie

p+q+r-s+t
p-q+r-t-u
p- q-r-t+u

Conclusion

Nous utilisons une simple pile pour garder une trace des drapeaux pour chaque ouverture de support. Ensuite, à l’aide de symboles, on transforme les valeurs une à une. La clé est de comprendre comment suivre les changements de symboles avec des parenthèses, et le problème devient alors plus facile.

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!