Problème pile - parenthésage

**rohim55** · 14/11/2006, 16h21

Salut. Je suis en première année d'école d'ingénieur et en cours on me demande d'évaluer une expression complètement paranthésée grâce aux piles.
Par exemple (4*(5-2)). On utilise deux piles, une pour les nombres et une autre pour les opérandes.
1. Lorsque l'on rencontre une paranthèse ouvrante, on l'ignore.
2. Lorsque l'on rencontre une valeur numérique, on l'empile dans la pile de réels.
3. Lorsque l'on rencontre un opérateur, on l'empile dans la pile de caractères.
4. Lorsqu'on rencontre une paranthèse fermante, on dépile un opérateur, on dépile deux valeurs numérique, on effectue le calcul et on empile le nouveau résultat dans la pile de réel.
5. Une fois toute l'expression parcourue, le résultat se trouve au sommet de la pile.
Pouvez vous me dire ce qui cloche, parce que sur le papier, mon code à l'air de marcher et ça fait plusieur jour que je m'acharne dessus.
Merci beaucoup d'avance.

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
 
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<locale.h>
 
void main()
{
	char tabc[4];
	float tabi[4];
	int i,j,k;
	char expression[20];
	printf("Programme-TP3 LAMOUROUX Damien (C) 3iL-A1\n");
	printf("-----------------------------------------\n\n");
	printf("Exemple: (4.5 + (-5 * 9.2))\n");
	printf("Entrez votre expression completement parenthesee:");	
	scanf("%s",&expression);
	fflush(stdin);
	i=0;
	j=0;
	k=0;
 
//-----------------------Parcours de la chaine et génération des piles-----------------
	do
	{		
			do
			{
				if((expression[i]=='0')||(expression[i]=='1')||(expression[i]=='2')||(expression[i]=='3')||(expression[i]=='4')||(expression[i]=='5')||(expression[i]=='6')||(expression[i]=='7')||(expression[i]=='8')||(expression[i]=='9'))
				{
					tabi[j]=(expression[i]-'0');
					j++;
				}
				else if(expression[i]=='+')
				{
					tabc[k]=expression[i];
					k++;
				}
				else if(expression[i]=='-')
				{
					tabc[k]=expression[i];
					k++;
				}
				else if(expression[i]=='*')
				{
					tabc[k]=expression[i];
					k++;
				}
				else if(expression[i]=='/')
				{
					tabc[k]=expression[i];
					k++;
				}
 
				i++;
 
			}while(expression[i]!=')');
 
 
//-------------------------------Calcul----------------------------------------
 
 
			if(tabc[i-1]='+')
			{
				tabi[i-2]=tabi[i-2]+tabi[i-1];
				k=k-1;;
				j=j-2;
			}
			else if(tabc[i-1]='-')
			{
				tabi[i-2]=tabi[i-2]-tabi[i-1];
				k=k-1;;
				j=j-2;
			}
			else if(tabc[i-1]='*')
			{
				tabi[i-2]=tabi[i-2]*tabi[i-1];
				k=k-1;;
				j=j-2;
			}
			else if(tabc[i-1]='/')
			{
				tabi[i-2]=tabi[i-2]/tabi[i-1];
				k=k-1;;
				j=j-2;
			}
			printf("%f\n",tabi[j]);
	}while(expression[i]!='\0');
 
 
 
//---------------------------------Affichage du résultat--------------------------
	printf("Le resultat est:%f",tabi[j]);
 
}

**fearyourself** · 14/11/2006, 16h29

Envoyé par rohim55

Salut. Je suis en première année d'école d'ingénieur et en cours on me demande d'évaluer une expression complètement paranthésée grâce aux piles.
Par exemple (4*(5-2)). On utilise deux piles, une pour les nombres et une autre pour les opérandes.
1. Lorsque l'on rencontre une paranthèse ouvrante, on l'ignore.
2. Lorsque l'on rencontre une valeur numérique, on l'empile dans la pile de réels.
3. Lorsque l'on rencontre un opérateur, on l'empile dans la pile de caractères.
4. Lorsqu'on rencontre une paranthèse fermante, on dépile un opérateur, on dépile deux valeurs numérique, on effectue le calcul et on empile le nouveau résultat dans la pile de réel.
5. Une fois toute l'expression parcourue, le résultat se trouve au sommet de la pile.

Exercice classique.

Pouvez vous me dire ce qui cloche, parce que sur le papier, mon code à l'air de marcher et ça fait plusieur jour que je m'acharne dessus.
Merci beaucoup d'avance.

Régle déjà ces warnings et je pense que tu seras mieux parti :

pile.c:7: warning: return type of 'main' is not 'int'
pile.c: In function 'main':
pile.c:16: warning: format '%s' expects type 'char *', but argument 2 has type 'char (*)[19u]'
pile.c:61: warning: suggest parentheses around assignment used as truth value
pile.c:67: warning: suggest parentheses around assignment used as truth value
pile.c:73: warning: suggest parentheses around assignment used as truth value
pile.c:79: warning: suggest parentheses around assignment used as truth value

Jc

**Thierry Chappuis** · 14/11/2006, 16h57

Salut,

En regardant d'un oeil en vitesse, je vois:

1. La forme de main n'est pas standard:

Code :

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

1
2
3
4
5
int main(void) 
/* ou */
int main(int argc, char *argv[])
 
/*mais main doit renvoyer un int */

2.fflush(stdin); n'est pas valide. On ne peut utiliser la fonction fftush pour purger le flux stdin.
3. Il est recommandé d'utiliser fgets à la place de scanf, scanf étant réservé aux experts dont je ne fais pas partie

Code :

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

fgets(expression, 20, stdin); /* à la place de scanf("%s", &expression);

4. En plus scanf("%s", &expression) n'est pas une syntaxe correcte. Sous cette forme, scanf n'est pas adaptée à la capture d'une ligne entrée par l'utilisateur. Cela n'engage que moi, mais n'utilise pas scanf mais fgets (voir ci-dessus).

Pour le reste de ton code, je vais essayer de m'y plonger.

Mujigkalement

Thierry

**Trap D** · 14/11/2006, 17h06

Salut
Ce code

Code :

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

			if((expression[i]=='0')||(expression[i]=='1')||(expression[i]=='2')||(expression[i]=='3')||(expression[i]=='4')||(expression[i]=='5')||(expression[i]=='6')||(expression[i]=='7')||(expression[i]=='8')||(expression[i]=='9'))

peut avantageusement être remplacé par

Code :

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

if (isdigit(expression[i]))

isdigit est déclaré dans ctype.h.
Autre conseil, utilise des fonctions aux noms "parlant", (style empiler_nombre, empiler_operande, calculer) ton code sera beaucoup plus lisible et proche du pseudo algo que tu as peut-être écrit.

**Thierry Chappuis** · 14/11/2006, 17h41

Salut,

Tu t'emmêles pas mal les pinceaux avec les indices i, j et k.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
if (tabc[k-1] == '+')  /* et non if (tabc[i-1]='+') */
{
    tabi[j-2] = tabi[j-2] + tabi[j-1]; /* et non tabi[i-2]=tabi[i-2]+tabi[i-1]; */
    k=k-1;;
    j=j-1;   /* et non j=j-2; */
}
else if (tabc[k-1] == '-') /* et non if (tabc[i-1]='-') */
{
    tabi[j-2] = tabi[j-2] - tabi[j-1]; /* et non tabi[i-2]=tabi[i-2]-tabi[i-1]; */
    k=k-1;;
    j=j-1; /* et non j = j-2; */
 }
/* etc. */

De plus, si l'utilisateur entre l'expression 3+5 qui n'a pas de parenthèses, tu ne sors jamais de la boucle intérieure.

Thierry

**Thierry Chappuis** · 14/11/2006, 18h22

Dans ta boucle intérieure, tu empiles dans tabc les opérateurs '+', '-', '*' et '/'. Par contre tu n'empiles dans tabi que des entiers entre 0 et 9 compris. Par contre si l'utilisateur entre un décimal comme:

Code :

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

Entrez votre expression completement parenthesee: (4.5 + 2)

ton programme est dans les choux!!!

La partie acquisition de l'expression est presque OK...

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
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<locale.h>
 
int main(void)
{
	char tabc[4] = {'\0'};
	float tabi[4] = {0};
	int i,j,k;
	char expression[30];
 
	/* Usage*/
	printf("Programme-TP3 LAMOUROUX Damien (C) 3iL-A1\n");
	printf("-----------------------------------------\n\n");
	printf("Exemple: (4.5 + (-5 * 9.2))\n");
 
	printf("Entrez votre expression completement parenthesee: ");
	fflush(stdout); /* Vide le tampon de la sortie standard */
	fgets(expression, 30, stdin);
 
        i= j = k = 0;
 
        /* ... */
        return EXIT_SUCCESS;
}

A mon avis la conception du reste du code est à revoir afin de gérer correctement les décimaux et les nombres négatifs. Attention également à la longueur des tableaux tabc et tabi. Dans ton programme, tu empiles tant que tu ne rencontres pas le caractèpre ')'. Si j'entre l'expression (1+2+3+4+5+6), qui est coreectement parenthésée, je dépasse la capacité des tableaux tabc et tabi.

Le mieux est de reprendre le problème avec un crayon et un papier et de voir quelles sont les situations (essaie d'être le plus exhaustif possible) que devra gérer ton code. Ensuite écrit l'algorithme en pseudocode, et l'implémentation en C te semblera évidente à quelques détails prêts pour lesquels nous sommes là pour t'aider.

Thierry

**koala01** · 14/11/2006, 22h45

Salut,

J'ai parcourru, tres rapidement, je dois l'avouer, ton code, et il m'a inspiré quelques remarques...

1- La succession de if(test)...eslse if(test)... est relativement indigeste...

Pourquoi ne pas utiliser la possiblité offerte par tous les langages de programmations récents connue sous le nom de "test à choix multiple", ce qui se traduit, en C, par une structure switch (variable) case valeur

2- on code devient rapidement indigeste du simple fait que tu fais tout dans une seule et meme fonction...

Retiens toujours que tu auras plus facile à t'y retrouver dans cinq fonctions de 50 lignes qui font chacune une chose et une seule, mais qui la font correctement que dans une seule et unique fonction de 250 lignes qui ferait le travail de ces 5 fonctions...

Ainsi, on pourrait prévoir une fonction pour chacune des opérations de base (additionne, soustrait, divise, multiplie) qui se contenterait d'effectuer cette opération

3-Le fait de ne prévoir de travailler qu'avec des entiers présente, comme signalé plus haut, une limite assez contraignante...

Sans meme envisager une formule du genre de (4.5+3), on peut, tout simplement envisager que l'utilisateur introduise (3/2)... ce qui enverra ton programme dans les choux... L'utilisation d'un type permettant de travailler avec des nombres décimaux me semblerait plus judicieuse

4- Tu parle de l'utilisation de =>piles<=, pourquoi ne pas, réellement utiliser une structure dynamique adaptée?

Bien sur, cela nécessite un effort de conception supplémentaire, mais, dans l'ensemble, cela te facilitera énormément la vie en supprimant la limitation du nombre d'operateurs/operandes...

Tu pourrais tres bien utiliser deux structures du genre de

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
typedef struct SPileOperateur
{
    char Operateur; /*un caractere ira tres bien ici ;) */
    struct SPileOperateur *Precedent; /* pour garder l'acces à l'élément qui 
                                     * a été rajouté juste avant */
 }PileOperateur;
typedef struct SPileValeur
{
    double Valeur; /* permettra d'avoir un résultat correct avec 3/2) */
    struct SPileValeur *Precedent;
}PileValeur;

Il te faudra, évidemment, les fonctions d'empilage et de dépilage pour tes deux structures...

Leur prototype serait

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
 
/*******************************************************
 **            Les fonctions d'empilage               **
 *******************************************************/
/* Empile un nouvel operateur et renvoie le pointeur sur le nouveau sommet
 * de la pile d'opérateurs
 * @operateur: valeur utile pour l'opérateur
 * @sommet: fournit le sommet de la pile avant l'ajout d'un nouvel opérateur
 */
PileOperateur* EmpileOperateur(char operateur, PileOperateur *sommet);
 
 
/* Empile une nouvelle valeur et renvoie le pointeur sur le nouveau sommet de 
 * la pile de valeurs
 * @valeur: valeur utile pour la valeur
 * @sommet: fournit le sommet de la pile avant l'ajout d'une nouvelle valeur
 */
PileValeur*  EmpileValeur(double valeur, PileValeur *sommet);
 
 
/*******************************************************
 **            Les fonctions de dépilage              **
 *******************************************************/
 
/* Dépile l'opérateur qui se trouve au sommet de la pile d'opérateurs et
 * renvoie un pointeur sur le nouveau sommet (AKA l'élément de la pile qui
 * avait été  inséré avant l'opérateur qu'on récupère avec la fonction) 
 * @ operateur: opérateur récupéré par la fonction (un pointeur pour pouvoir
 *              modifier la valeur du caractere dans la fonction appelante
 * @ sommet: sommet de la pile avant qu'on enleve l'opérateur qui s'y trouve
 */
PileOperateur* DepileOperateur(char *operateur, PileOperateur *sommet);
 
/* Dépile la valeur qui se trouve au sommet de la pile de valeurs et renvoie un
 * pointeur sur le nouveau sommet (AKA l'élément de la pile qui avait été
 * inséré avant la valeur qu'on récupère avec la fonction) 
 * @ valeur: valeur récupérée par la fonction (un pointeur pour pouvoir
 *           modifier la valeur du double dans la fonction appelante
 * @ sommet: sommet de la pile avant qu'on enleve la valeur qui s'y trouve
 */
PileValeur* DepileValeur(double *valeur,PileValeur *sommet);

Leur implémentation serait du genre de

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
 
/*******************************************************
 **            Les fonctions d'empilage               **
 *******************************************************/
 
PileOperateur* EmpileOperateur(char operateur, PileOperateur *sommet)
{
/* premiere chose: allouer la mémoire pour un nouvel élément de la pile... */
    PileOperateur *nouveau=malloc(sizeof(PileOperateur));
/* Et vérifier si l'allocation a réussi */
    if(nouveau==NULL)
    {
         /* L'allocation a raté, autant renvoyer sommet tout de suite 
          * (mais il y a peut etre quelque chose à faire???) 
          */
        return sommet;
    } 
/* si on arrive ici, on est sur que l'allocation a réussi... on peut donc travailler
 * serainement */
    /* on défini la valeur adéquate */
    nouveau->Operateur=operateur;
    /* on rajoute le nouvel élément au sommet de la pile */
    nouveau->Precedent=sommet;
    /* on renvoie le nouveau sommet de la pile (CAD nouveau) */
    return nouveau;
}
/* meme principe pour l'empilage des valeurs (je "zape" les commentaires ;) */
PileValeur*  EmpileValeur(double valeur, PileValeur *sommet)
{
    PileValeur *nouveau=malloc(sizeof(PileValeur));
    if(nouveau==NULL)
    {
        return sommet;
    } 
    nouveau->Valeur=valeur;
    nouveau->Precedent=sommet;
    return nouveau;
}
/*******************************************************
 **            Les fonctions de dépilage              **
 *******************************************************/
 
PileOperateur* DepileOperateur(char operateur, PileOperateur *sommet)
{
    /* une variable temporaire */
    PileOperateur *tempo;
    /* La pile ne doit pas etre vide... */
    if(sommet==NULL)
        return sommet;
/* si on arrive ici, c'est que la pile d'opérateurs n'était pas vide...
 * on peut donc travailler serainement */
    /* on fournit la valeur de sommet->Operateur à l'"élément pointe par
     * operateur"*/
    *operateur=sommet->Operateur;
    /* tempo prend l'élément qui se trouve juste "en dessous" de celui sur 
     * lequel on travaile actuellement (celui qui a été inséré avant, en fait)
     */
    tempo=sommet->Precedent;
    /* on peut libérer sommet sans risque */
    /* en commencant par lui retirer tout contact avec la pile */
    sommet->Precedent=NULL;
    free(sommet);
    /* on renvoi tempo, qui est devenu le nouveau sommet de la pile */
    return tempo;
}
/* meme principe pour le dépilage des valeurs (je "zape" les commentaires ;) */
PileOperateur* DepileOperateur(double *valeur, PileOperateur *sommet)
{
    PileVariable *tempo;
    if(sommet==NULL)
        return sommet;
    *valeur=sommet->Valeur;
    tempo=sommet->Precedent;
    sommet->Precedent=NULL;
    free(sommet);
    return tempo;
}

L'appel de ces différentes fonctions se ferait dans un code ressemblant à 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
 
void unefonction()
{
    /* Le sommet de la pile d'opérateur (qui ne pointe sur rien au départ)*/
    PileOperateur *SommetOp=NULL;
    /* Le sommet de la pile de valeurs (qui ne pointe sur rien au départ)*/
    PileValeur* SommetVal=NULL;
    /* des pointeurs temporaires (pour la vérification) */
    PileOperateur *TempoOp;
    PileValeur *TempoVal;
    /* un double pour les valeurs */
    double valeur;
    /* et un caractère pour les operateurs */
    char op;
    /* ajout d'un opérateur à la pile d'opérateurs, avec vérification intégrée*/
    if((TempoOp=EmpileOperateur(op,SommetOp))!=SommetOp)
    {
        /* ici, ca a marché... le nouveau sommet officiel de la pile d'opérateurs
         * est le sommet qu'on vient de récupérer */
        SommetOp=TempoOp;
    }
    else
    {
        /* ici, ca a "foiré" */
    }
    /* ajout d'une valeur à la pile de valeurs, avec vérification intégrée */
    if((TempoVal=EmpileValeur(valeur,SommetVal))!=SommeVal)
    {
        /* ici, ca a marché... le nouveau sommet officiel de la pile de valeurs
          * est celui qu'on vient de récupérer*/
        SommetVal=TempoVal;
    }
    else
    {
        /* ici, ca a "foiré" */
    }
/* pour le dépilage, il faudra passer respectivement l'adresse de op et
 * l'adresse de Valeur, mais le principe sera sensiblement le meme:*/
    /* Récupération de l'opérateur qui se trouve au sommet de la pile avec
     * vérification intégrée */
    if((TempoOp=DepileOperateur(&op,SommetOp))!=SommetOp)
    {
        /* ici, ca a marché, et op a recu la valeur de l'ancien sommet de la pile
         * des opérateurs... il faut juste voir ce qu'on en fait... sans oublier
         * de changer le sommet officiel de notre pile ;) */
    }
    else
    {
        /* ici, ca a "foiré"... */
    }
    /* Récupération de la vaeur qui se trouve au sommet de la pile avec
     * vérification intégrée */
    if((TempoVal=DepileValeur(&valeur,SommetVal))!=SommetValeur)
    {
        /* ici, ca a marché, et valeur a recu la valeur de l'ancien sommet de la
         *  pile des valeurs... il faut juste voir ce qu'on en fait... sans
         * oublier de changer le sommet officiel de notre pile ;) */
    }
    else
    {
        /* ici, ca a "foiré"... */
    }
}

Comme, une fois n'est pas coutume, je me suis laissé entrainer par ma verve, je vai m'arreter ici...

Je t'ai donné des codes corrects et toutes les informations qui pourraient te servir pour travailler efficiacement...

A toi de voir si l'idée te plait

Problème pile - parenthésage

C

Discussions similaires

Partager

Partager