, je suis un étudiant en 2eme année MIAGE et je cherche un algorithme qui me permet de calculer une chaine postfixée (exp:43+23*/) ou prefixée (/+43*23) en utilisant des piles
SVP aidez moi
, je suis un étudiant en 2eme année MIAGE et je cherche un algorithme qui me permet de calculer une chaine postfixée (exp:43+23*/) ou prefixée (/+43*23) en utilisant des piles
SVP aidez moi
En postfixé : on parcourt la chaîne et lorsqu'on tombe sur un opérateur, on prend les n opérandes situés devant l'opérateur, n étant le nombre d'opérandes requis par l'opérateur, on évalue le tout puis on les remplace (les n opérandes et l'opérateur) par le résultat. On s'arrête lorsqu'il ne reste plus qu'un mot. Par exemple :
En préfixé c'est aussi le même raisonnement
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3 1 2 * 3 + --> 2 3 + --> 5
voici l'algo que j'ai pu faire
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175 #include<stdio.h> #include<stdlib.h> #include<string.h> #include<ctype.h> #include "pile.h" int main () { Pile *tas; char *ch,a,b,c; int i,ne,ne1,ne2; if ((tas = (Pile *) malloc (sizeof (Pile))) == NULL) return -1; if ((ch=(char*) malloc (sizeof (char))) == NULL) return -1; initialisation (tas); printf("Saisir une chaine postfixe a calculer : \t"); gets(ch); affiche(tas); printf("-------------------------------\n"); c=0; for(i=0;i<sizeof(ch);i++) { if (isdigit(ch[i])) { empiler(tas,ch); } else { switch(ch[i]) { case'+':{a=*tas->debut->donnee ; tas->debut->suivant; b=*tas->debut->donnee; depiler(tas); depiler(tas); ne=atoi(&a); ne1=atoi(&b); ne2=ne+ne1; c=(char)ne2; empiler(tas,&c);} case'-':{a=*tas->debut->donnee ; tas->debut->suivant; b=*tas->debut->donnee; depiler(tas); depiler(tas); ne=atoi(&a); ne1=atoi(&b); ne2=ne-ne1; c=(char)ne2; empiler(tas,&c);} case'*':{a=*tas->debut->donnee ; tas->debut->suivant; b=*tas->debut->donnee; depiler(tas); depiler(tas); ne=atoi(&a); ne1=atoi(&b); ne2=ne*ne1; c=(char)ne2; empiler(tas,&c);} case'/':{a=*tas->debut->donnee ; tas->debut->suivant; b=*tas->debut->donnee; depiler(tas); depiler(tas); ne=atoi(&a); ne1=atoi(&b); ne2=ne/ne1; c=(char)ne2; empiler(tas,&c);} } } } printf("le resultat de votre calcul est :"); affiche(tas); return 0; } /*********************\ * pile * \*********************/ typedef struct ElementListe{ char *donnee; struct ElementListe *suivant; } Element; typedef struct ListeRepere{ Element *debut; int taille; } Pile; /* initialisation */ void initialisation (Pile *tas); /* EMPILER*/ int empiler (Pile *tas, char *donnee); /* DEPILER*/ int depiler (Pile *tas); /* Affichage de élément en haut de la pile (LastInFirstOut) */ #define pile_donnee(tas) tas->debut->donnee /* Affiche la pile */ void affiche (Pile *tas); /***********************\ * pile_function * \***********************/ void initialisation (Pile * tas){ tas->debut = NULL; tas->taille = 0; } /* empiler (ajouter) un élément dans la pile */ int empiler (Pile * tas, char *donnee){ Element *nouveau_element; if ((nouveau_element = (Element *) malloc (sizeof (Element))) == NULL) return -1; if ((nouveau_element->donnee = (char *) malloc (sizeof (char))) == NULL) return -1; strcpy (nouveau_element->donnee, donnee); nouveau_element->suivant = tas->debut; tas->debut = nouveau_element; tas->taille++; return 0; } /* depiler (supprimer un élément de la pile */ int depiler (Pile * tas){ Element *supp_element; if (tas->taille == 0) return -1; supp_element = tas->debut; tas->debut = tas->debut->suivant; free (supp_element->donnee); free (supp_element); tas->taille--; return 0; } /* affichage de la pile */ void affiche (Pile * tas){ Element *courant; int i; courant = tas->debut; for(i=0;i<tas->taille;++i){ printf("\t\t%s\n", courant->donnee); courant = courant->suivant; } } }
Compiling...
Skipping... (no relevant changes detected)
postfixe.cpp
postfixe.obj - 0 error(s), 0 warning(s)
mais le problem lorsque j'appui sur entrer il y a un msg d'erreurs qui s'affiche !!
debug erreurs !
program:........postfixe.exe
damage:after normal block (#48) at 0X00A11D70
- Montre le contenu de pile.h (et les autres de fichiers de ton projet). On ne sait pas ce que t'as mis dedans.
- Inutile de caster le retour de malloc en C. malloc retourne un void *, type compatible avec tous les pointeurs.
- Remplace gets par fgets
-Ecris plutôt :
Code : Sélectionner tout - Visualiser dans une fenêtre à part while(ch[i]!=NULL)-
Code : Sélectionner tout - Visualiser dans une fenêtre à part while(ch[i] != '\0')Ah non, ça c'est pas du C. Tu peux utilier isdigit de ctype.h pour savoir si un caractère est bien un chiffre, mais pas ça.
Code : Sélectionner tout - Visualiser dans une fenêtre à part if (ch[i]=='0..9')
Mais où est ton message d'erreur ? Mais où est pile.h ?
PS: Appeler "tas" une pile, ça fait mauvais genre. Le mot "tas" a une signification particulière en C, et c'est pratiquement à l'opposé d'une pile...
Au fait quand j'y pense je ne comprends pas pourquoi tu as besoin d'une pile pour évaluer une expression post fixée. Normalement, on a besoin de pile que pour postfixer une expression. Pour évaluer, on fait comme je t'ai déjà dit, aucunement besoin d'une pile. Les mots doivent être séparés par un espace (ou n'importe quel autre caractère libre). Par exemple, la forme postfixée de :
est :
Code : Sélectionner tout - Visualiser dans une fenêtre à part (1 + 2) * 3Evaluer une telle expression est très simple (j'ai déjà expliqué plus haut). Voici un exemple (à améliorer) :
Code : Sélectionner tout - Visualiser dans une fenêtre à part 1 2 + 3 * /* = 9 */
Déclarations :
main :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5 #include <stdio.h> #include <stdlib.h> #include <string.h> double evaluer(double a, double b, char operation);
La fonction evaluer :
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 int main() { char s[100], s1[100], s2[100], op, seps[] = " \t\n", * p; double a, b; printf("Saisir une chaine postfixee a calculer : \t"); fgets(s, sizeof(s), stdin); p = strtok(s, seps); if (p != NULL) { strcpy(s1, p); a = atof(s1); p = strtok(NULL, seps); while (p != NULL) { strcpy(s2, p); b = atof(s2); p = strtok(NULL, seps); if (p != NULL) { op = *p; a = evaluer(a, b, op); p = strtok(NULL, seps); } } } printf("%f\n", a); return 0; }
On peut tester, ça marche (sauf si on entre n'importe quoi ...). Toutefois :
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 double evaluer(double a, double b, char operation) { double c; switch(operation) { case '+': c = a + b; break; case '-': c = a - b; break; case '*': c = a * b; break; case '/': c = a / b; break; default: c = 0; break; } return c; }
- Ce code n'est pas optimisé. Il y a pas mal de variables qu'on aurait pu ne pas déclarer mais le code serait (peut-être) moins lisible.
- Gestion d'erreurs quasi inexistante
@Melem: Je ne pense pas que sans pile, on puisse calculer un truc du genre:
1 2 + 3 4 - *.
Ah c'est vrai. Vraiment désolé. Comme on peut le constater d'après le code, j'ai supposé qu'un expression est toujours de la forme arg arg op arg op arg op ... arg op. Je me suis un peu précipité. En fait la solution qui marche (et qui utilise une pile ) est beaucoup plus simple : On empile les opérandes et on exécute les opérations (exécuter = retirer deux opérandes de la pile, faire l'opération et empiler le résultat).
main :
- number(const char * s, double * buf) teste si s est bien l'expression d'un nombre et si tel est le cas, la convertit en double et place le résultat dans la variable pointée par buf. Cette fonction utilise simplement strtod.
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 int main() { char s[100], op, seps[] = " \t\n", * p; double x; printf("Saisir une chaine postfixee a calculer : \t"); fgets(s, sizeof(s), stdin); p = strtok(s, seps); while (p != NULL) { if (number(p, &x)) empiler(x); else /* si c'est pas un nb c'est un op */ { op = *p; executer(op); } p = strtok(NULL, seps) } depiler(&x); printf("%f\n", x); return 0; }
- empiler(double x) empile x
- depiler(double * buf) retire l'élément au sommet de la pile et le place dans la variable pointée par buf.
- executer(char op) retire deux éléments de la pile, fait l'opération (switch(op)) et empile le résultat.
Avec les fonctions citées ci-dessus bien écrites, ça devrait marcher.
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager