comment faire une optimisation itérative

Version imprimable

bonjour,

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

voici le code:

Code:

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:

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?

02/03/2009, 08h58
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é.
02/03/2009, 10h19
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).

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

Code:

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;
}

04/03/2009, 09h06
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:

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; }
06/03/2009, 21h35
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?
06/03/2009, 22h34
Gruik

Oui, le "man" (commande "man" sous unix, et également disponible un peu partout sur le web)
http://man.developpez.com/
Section 3 pour tout ce qui est bibliothèque standard du C, section 2 pour fonctions système unix.
Une page de man peut documenter une fonction ou un groupe de fonctions standard du C.
http://man.developpez.com/man3/exit.3.php
http://man.developpez.com/man3/getchar.3.php
Certains headers ont leur page de man dédiée ( mais pas sur dvp :? )
07/03/2009, 13h46
emmesse

merci

mon problème est résolu et je vous remercie à chacun d'avoir participé à cette discussion

à bientôt...