Vérification du parenthèsage (méthode récursive)

Version imprimable

07/12/2005, 15h20
Saiyan

Vérification du parenthèsage (méthode récursive)

Bonjour j'ai un petit problème de vérification de parenthèsage sous c++ builder.

Le principe est d'écrire une méthode récursive qui indique si le parenthèsage est correct.
Par exemple :
( ( [] ) ) : correct
( ( [ ) ( ) ] ) : incorrect
( [ [ ] ] ( ) : incorrect

Une petite description : on a une liste L (qui affiche plusieurs lignes dans un Memo) et il faut tester les lignes du Mémo et indiquer si le parenthèsage est correct. je préfère ne pas supprimer les parenthèses déja testées ( avec L.delete(1,1) par ex).

Si quelqu'un a une idée. Merci d'avance Développez.com :p

Je pense que le code suivant fonctionne:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool TestPar(char **bc, char c=0)
 {
   char prov;
   while (**bc!= 0)
   {
    prov =**bc;
    (*bc)++;
    switch (prov)
     {
      case '('  :
      case '['  : if(!TestPar(bc,prov)) return false;
                     break ;
      case ')'  : return c=='(';
      case ']'  : return c=='[';
      case  0   : return c==0 ;
      default   : ;
     }
   }
  return c== 0 ;
}

Avec pour appel :

Code:

1
2
3
4
  char * t = "xx(aa[bb]cc(dd)ee)z[ff([(vv)])]dd";
  char * bb=t;
  bool res = TestPar(&bb);
  if(!res)cout << setfill('-') << setw( bb-t) << right <<'!' << endl;

en retour, si il y a une erreur, bb pointe sur le caractère fautif

12/12/2005, 17h04
Saiyan

Merci, c'est nickel !

Seul problème, on m'a dit que char * ne peut pas etre utilisé.... et qu'il faudrait utiliser AnsiString... un type que l'on a défini à l'en-tete du programme.

Indication (en tete du programme) :

Citation:

const AnsiString VIDE = "|";
typedef AnsiString Liste;
Liste L1 = VIDE;

Dans le programme APPEL DE LA PROCEDURE (j'ai donc utilisé ton code :)) :

Citation:

char (je voudrais un AnsiString à la place) * t = "xx(aa[bb]cc(dd)ee)z[ff([(vv)])]dd";
char (je voudrais un AnsiString à la place) * bb=t;
bool res = TestPar(&bb);
if (res) Form1->Edit1->Text = "1" ;
else Form1->Edit1->Text = "0";

Citation:

Seul problème, on m'a dit que char * ne peut pas etre utilisé.... et qu'il faudrait utiliser AnsiString... un type que l'on a défini à l'en-tete du programme

L'utiliser exactement pour quoi faire ? Au minimum :
Code:

1 2 3 4 5 AnsiString t ="xx(aa[bb]cc(dd)ee)z[ff([(vv)])]dd"; char * bb= t.c_str(); bool res = TestPar(&bb); if (res) Form1->Edit1->Text = "1" ; else Form1->Edit1->Text = "0";
Si l'AnsiString doit être utilisé comme argument de TestPar, on a par exemple :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 bool TestPar(AnsiString & s, char c=0) { char prov; while (s.Length()!=0) { prov =s[1]; s.Delete(1,1); switch (prov) { case '(' : case '[' : if(!TestPar(s,prov)) return false; break ; case ')' : return c=='('; case ']' : return c=='['; case 0 : return c==0 ; default : ; } } return c== 0 ; }; ..... AnsiString t ="x]x(aa[bb]cc(dd)ee)z[ff([(vv)])]dd"; bool res = TestPar(t);
la fonction va être plus lourde (Appels à s.Length() et s.Delete()) et dans cette version, l'Ansistring de départ est détruit (mais on évite la création d'AnsiString intermédiares). En cas d'erreur, L'AnsiString contient le reste de la chaîne après l'erreur

12/12/2005, 18h52
Djob

Cet algo est vraiment bien fait, :bravo:
c'est vrai que le premier est plus optimisé,

mais si je peux me permettre ,suite à la version AnsiString que tu proposes:
il est peut être possible d'eviter la destruction de l'ansistring et l'utilisation de Delete() en gérant un indice :

Code:

bool TestPar(AnsiString s,int &indice,char c=0)

ainsi que le recalcul de la taille
en le calculant qu'une fois avant la boucle (puisqu'avec un indice on a plus besoin de supprimer);

Code:

int taille =s.Length();
12/12/2005, 22h09
diogene
Djob :

Citation:

Cet algo est vraiment bien fait,

Merci :D

Citation:

mais si je peux me permettre ,suite à la version AnsiString que tu proposes:
il est peut être possible d'eviter la destruction de l'ansistring et l'utilisation de Delete() en gérant un indice :

Oui, j'ai d'ailleurs hésité entre les deux possibilités. Mais j'ai donné cette version parce qu'elle n'a pas de variable "extérieure" à définir par l'utilisateur de la fonction. Alors, tant qu'à ne pas "optimiser", autant faire plus propre pour l'utilisateur. Mais c'est vrai que le Delete dans la fonction récursive me chagrine plus que la destruction de l'AnsiString à laquelle il est peu couteux de remédier
Code:

1 2 3 AnsiString s ="x]x(aa[bb]cc(dd)ee)z[ff([(vv)])]dd"; AnsiString t = s; bool res = TestPar(t);
14/12/2005, 16h36
Saiyan

Haaaa je vois ! Effectivement ça fonctionne bien !

Mais comment faire pour tester une liste ?
J'ai une liste L1 (aussi affichée dans un Memo) que je voudrais tester, j'ai essayé de prendre les lignes du Memo pour les concaténer et les tester, sans succès :?

En fait, au lieu de

Citation:

AnsiString s ="x]x(aa[bb]cc(dd)ee)z[ff([(vv)])]dd";

Il faut que je test une liste :?
14/12/2005, 16h54
Saiyan

C'est bon j'ai réussi !! :D

Merci pour votre aide :wink: