Discussion :

[emmesse]

bonjour,

sachant que :
PO=parenthèse ouvrante
AC=autre caractère
PF=parenthèse fermante

voici le code:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
void reste(){
   if(symbole==AC||symbole==PO){
      element();
      reste();
   }
}
void element(){
   if(symbole==AC)
      accepter(AC);
   else{
      accepter(PO);
      reste();
      accepter(PF);
   }
}

On peut optimiser comme ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
void reste(){
   while(symbole==AC||symbole==PO){
      if(symbole==AC)
         accepter(AC);
      else{
         accepter(PO);
         reste();
         accepter(PF);
      }
   }
}

je voudrais rendre la fonction reste totalement itérative.

Quelqu'un a une idée?

[Invité(e)]

Bonjour,

Le problème n'est pas très clair...
Quel algorithme a permis d'écrire le code posté ?
Qu'y-a-t-il dans la fonction accepter ?

Sinon, sans parler d'optimisation, il est toujours possible de transformer un algorithme récursif en l'équivalent itératif. Le faire avec du code est plus compliqué.

[Médinoc]

Dans la première version du code, la récursivité de reste() est terminale, donc l'optimisation doit être plus facile (puisque certains compilos sont capables de la faire eux-mêmes).

[emmesse]

j'ai travaillé la dessus la nuit dernière et j'ai fait comme ceci:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <stdio.h>
/*
chaine -> suite_AC | ( chaine ) | FIN
suite_AC -> AC suite_AC | rien
*/
typedef enum {AC,PO,PF,FIN} U_LEX;
 
U_LEX symbole;
 
void chaine();
void suite_AC();
void accepter(U_LEX lex);
U_LEX analex();
 
main(){
   symbole=analex();
   chaine();
}
 
void chaine(){
   int nbPF=0;
   while(1){
      if(symbole==AC)
         while(symbole==AC)
            accepter(AC);
      else if(symbole==PO){
         accepter(PO);
         nbPF++;
      }
      else if(symbole==PF){
         accepter(PF);
         nbPF--;
         if(nbPF<0){
            fprintf(stderr,"parenthèses mal équilibrées : parenthèse fermante en trop\n");
            exit(1);
         }
      }
      else if(symbole==FIN)
         if(nbPF==0){
            accepter(FIN);
            fprintf(stdout,"parenthèses équilibrées\n");
            exit(0);
         }
         else{
            fprintf(stderr,"parenthèses mal équilibrées : manque une parenthèse fermante\n");
            exit(1);
         }
   }
}
 
void accepter(U_LEX lex){
   if(symbole==lex){
      if(lex!=FIN)
         symbole=analex();
   }
   else{
      fprintf(stderr,"parenthèses mal eqilibrées : manque une parenthèse fermante\n");
      exit(2);
   }
}
 
U_LEX analex(){
   char T;
   T=getchar();
   if(T=='(')
      return PO;
   else if(T==')')
      return PF;
   else if(T=='\n')
      return FIN;
   else
      return AC;
}

[Invité(e)]

Ca a l'air de fonctionner...

quelques remarques sur le code :
ajouter #include <stdlib.h> pour la déclaration de exit.

Si une fonction ne prend pas de paramètre, on met void, main est de type int.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
void chaine(void);
void suite_AC(void);
void accepter(U_LEX lex);
U_LEX analex(void);
 
int main(void){
   symbole=analex();
   chaine();
   return 0;
}

[emmesse]

merci pour stdlib, je me demandais quelle était l'entête pour exit

sinon, existe-t-il une documentation sur les".h" et leurs fonction?