Discussion :

[thegame]

, 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

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

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

1
2
3
    1 2 * 3 +
--> 2 3 +
--> 5

En préfixé c'est aussi le même raisonnement

[thegame]

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

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

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

while(ch[i]!=NULL)

Ecris plutôt :

Code :

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

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

-

Code :

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

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.

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

[Melem]

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 :

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

(1 + 2) * 3

est :

Code :

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

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 :

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

main :

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

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

[Médinoc]

@Melem: Je ne pense pas que sans pile, on puisse calculer un truc du genre:
1 2 + 3 4 - *.

[Melem]

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 :

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

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