Algorithme calcul postfixé, prefixé en utilisant les piles

Version imprimable

19/03/2008, 20h51
thegame

Algorithme calcul postfixé, prefixé en utilisant les piles

:salut:, 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
20/03/2008, 14h14
Melem
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 :
Code:

1 2 3 1 2 * 3 + --> 2 3 + --> 5
En préfixé c'est aussi le même raisonnement

voici l'algo que j'ai pu faire

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

27/03/2008, 13h59
Melem

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

Code:

while(ch[i]!=NULL)

Ecris plutôt :

Code:

while(ch[i] != '\0')

-

Code:

if (ch[i]=='0..9')

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.
27/03/2008, 13h59
Médinoc

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 :

Code:

(1 + 2) * 3

est :

Code:

1 2 + 3 * /* = 9 */

Evaluer une telle expression est très simple (j'ai déjà expliqué plus haut). Voici un exemple (à améliorer) :

Déclarations :
Code:

1 2 3 4 5 #include <stdio.h> #include <stdlib.h> #include <string.h> double evaluer(double a, double b, char operation);
main :
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 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; }
La fonction evaluer :
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 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; }
On peut tester, ça marche (sauf si on entre n'importe quoi ...). Toutefois :

- 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

28/03/2008, 09h05
Médinoc

@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 :lol:) 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 :
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 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; }
- 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.

- 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.