cs_Styxounet
Messages postés2Date d'inscriptionmardi 18 février 2003StatutMembreDernière intervention18 février 2003
-
18 févr. 2003 à 11:42
jonathanmcdougall
Messages postés64Date d'inscriptiondimanche 9 février 2003StatutMembreDernière intervention 7 mars 2003
-
19 févr. 2003 à 02:33
Salut, j'ai une équation de ce genre...
((((4)*(((X)^(4-1)-((5)))*(X)+(((X^4-5*X+2)))*((X^2+1))-((2)*((X)^(2-1))*(((X^4-5*X+2)*X)))/((X^2+1))²
Vous l'aurez remarqué il y a un ptit surplus niveau parentaises... Je cherche un algorithme pour détecter si une parenataise est inutile, pour pouvoir la supprimer le cas échéant.
Une idée? :)
jonathanmcdougall
Messages postés64Date d'inscriptiondimanche 9 février 2003StatutMembreDernière intervention 7 mars 2003 19 févr. 2003 à 02:33
> > > Salut, j'ai une équation de ce genre...
> > > ((((4)*(((X)^(4-1)-((5)))*(X)+(((X^4-5*X+2)))*((X^2+1))-((2)*((X)^(2-1))*(((X^4-5*X+2)*X)))/((X^2+1))²
> > > Vous l'aurez remarqué il y a un ptit surplus niveau parentaises... Je cherche un algorithme pour détecter si une parenataise est inutile, pour pouvoir la supprimer le cas échéant.
> > > Une idée? :)
>
> > Salut,
> > une idee bien entendu, se nomme ecrire un parser.
> > Au boulot.
> > ciao...
> >
> Non je ne veux pas de parser, il me simplifierai l'équation... (et c'est pas mon but)
> Je veux juste retirer les parentaises inutiles :)
Le terme "to parse" est en fait de "tokenizer", de prendre chaque partie (le mot 'partie' dépend du contexte) d'une string et de la mettre à part. Le fait de "parser" ton équation serait simplement de mettre chaque opérateur ou valeur dans un vector et de les analyser.
C'est assez simple comme algorithme :
# include <vector>
# include <string>
//parse une string 'equation' et retourne un vector de
//tokens
std::vector<std::string> parse(std::string equation)
{
//le vector qui contiendra chaque opérateur ou valeur (les
//tokens)
std::vector<std::string> v;
//une string temporaire pour construire des tokens de plus
//d'un caractère (un chiffre par exemple)
std::string temp;
//lorsque tu trouves un caractères qui peut potentiellement
//ne pas être seul dans un même token, tu met 'flag' à
//true. Par exemple, lorsque tu tombes sur un chiffre,
//disons 4, ce n'est pas nécessairement un token, car
//c'est peut-être en fait 4586. 'flag' est remis à false lorsque
//le token est complet
bool flag = false;
//contient les caractères un à un d'equation
char c;
//on boucle sur chaque caractère de l'équation
for (int i=0; i<equation.size(); i++)
{
//on prend le caractère 'i'
c = equation[i];
//on teste ce caractère
switch (c)
{
// case opérateur arithmétique
// case parenthèses
// ...
// si le flag est true, ça veut dire qu'on était en train de
// construire un chiffre
// Puisqu'on a trouvé un opérateur, le chiffre
// est terminé :
v.push_back(temp); //ajout du token
temp = ""; //le token est terminé
flag = false; //on ne construit plus un token
// sinon, on met tout simplement l'opérateur
v.push_back(c);
break;
// case chiffre
// mettre un flag à true, car il y a peut-être d'autres chiffres
// après celui-ci
flag = true;
temp += c;
}
return v;
}
Maintenant, nous avons un vector de tokens qui pourrait ressembler à ça :
Tu comprends maintenant l'utilité du flag? Sans celui-ci, les chiffres de '568' et de '21' auraient été séparés.
Maintenant, tu n'as qu'à faire le compte des parenthèses : lorsque deux parenthèses se ferment une après l'autre, tu vérifies si elles avaient été ouvertes aussi une après l'autres (comme ici, v[0] et v[1] ainsi que v[5] et v[6]). Si oui, tu en enlèves une paire.