Evaluation d'une expression arithmétiqueà partir de sa notation post-fixé (en dev c++

**zoheirrr** · 03/05/2007, 17h25

Salut à tous!
Voici un exo qu'on nous a demandé de préparé mais franchement je ne sais pas comment commencer
Aidez-moi s'il vous plaît!

La notation post-fixée est obtenue de la façon suivante:
1. L'expression arithmétique est représentée par un arbre binaire
2. Un parcours de l'arbre en pré-ordre permet d'afficher l'expression en notation post-fixée

Etapes à réaliser :1. Mémoriser une expression donnée en notation post-fixée dans une file représentée par chaînage. Chaque maillon de la file aura pour valeur un opérande de type réél ouun opétratuer binaire (+,-,*,/).
2. Parcourir cette file pour afficher l'expression post-fixée.
Evaluer l'expression en utilisant une pile représentée par contiguité. Afficher la trace de l'évaluation.

Exemple:
L'expression (5*3/(1+4))-(7*2)
Trace de son évaluation:
empiler 5, empiler 3, dépiler 3, dépiler 5, empiler 15(5*3), empiler 1, empiler 4, dépiler 4, dépiler 1, empiler 5(1+4), dépiler 5, dépiler 15, empiler 3(15/5), empiler 7, empiler 2, dépiler 2, dépiler 7, empiler 14(7*2), dépiler 14, dépiler 3, empiler -11 (3-14)

Il n'est pas nécessaire d'afficher les expressions entre parenthèses qui figurent dans l'exemple ci de-ssus.

**TheGzD** · 03/05/2007, 18h24

Pour commencer tu dois décider de la structure de données détaillée que tu vas utiliser, c'est-à-dire de la façon dont ta liste chaînée va te permettre d'implémenter ton arbre. Je te conseille d'essayer de réprésenter ton exemple sous cette forme dans un premier temps. Ton algo de parcourt devrait te paraître évident quand tu auras fait ça.
En ce qui concerne le parcourt en lui même : sais-tu exactement ce qu'est un parcourt post-fixé ? (pas que je ne le sache pas, mais il faut que toi tu le saches ^^)

**bruno_pages** · 03/05/2007, 19h55

bienvenue sur Developpez

zoheirrr, c'est TRES simple à faire, comme le propose TheGzD pense à une structure de donnée EVIDENTE qui colle au probleme. Je ne vais pas te faire la résolution parce qu'il faut 1000 fois mieux trouver pas soi même, mais il suffit juste de se demander ce qu'est une expression ... et surtout de penser récursif!

**zoheirrr** · 03/05/2007, 23h17

J'aimerai vous demander la structure des piles, des files et des listes (enfin tous les trucs nécessaires dans ce programme) en langage dev C++. Merci d'avance

**bruno_pages** · 03/05/2007, 23h52

zoheirrr, encore une fois on ne fera pas l'exo a ta place, car ce n'est pas lui qui compte mais ce que tu vas apprendre en le faisant

par contre tu peux proposer des solutions et on te dira ce qu'on en pense

**zoheirrr** · 03/05/2007, 23h59

Ok lol... Merci quand même, vuos ne m'aidez pas trop

lol

**TheGzD** · 10/05/2007, 10h37

Il va nous être difficile de t'aider plus si tu n'y mets pas plus de bonne volonté ...

**zoheirrr** · 11/05/2007, 16h48

Voilà je l'ai fait, mais j'ai besoin de votre aide, car j'ai un problème de compilation, voilà

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
176
177
178
179
180
181
182
183
184
185
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#define lmax 200                      
/*----Declaration de la file----*/ 
 
typedef struct maillon *maillon_ptr;
typedef struct maillon
{
        int val;maillon_ptr lien;
}
maillon;
 
typedef struct file
{
        maillon_ptr debut;
        maillon_ptr fin;
}
file;
file f;
 
/*----declaration de la pile puis l'affichage----*/
typedef struct pile
{
     int t[lmax];
     unsigned int sommet;
}
pile;
 
typedef pile p;
 
void pile_vide (pile *p)
{
    p->sommet=0;
}
 
int est_vide(pile *p) 
{
    if (p->sommet==0)
    {
      return 1;
    }
    else
    { 
      return 0;
    }
}
 
int sommet (pile*p)
{
    if (est_vide(p)==1)
    {
      printf("erreur pile vide\n");
    }
    else (p->sommet=p->t[p->sommet]);
}
 
void empiler(pile *p,int e)
{
    if (p->sommet==lmax)
    {
      printf("erreur pile pleine\n");
    }
    else (p->sommet=p->sommet+1);
    (p->t[p->sommet]=e);                   
}
 
int depiler (pile *p)
{
    if (est_vide(p)==1)
    {
      printf("erreur pile vide\n");
    }
    else 
    {
      (p->sommet=p->sommet-1);
    } 
}
 
void afficher (pile p)
{
    int i;
    printf ("on va afficher la pile :\n");
    for (i=1;i<=p.sommet;i++)
    {
      printf("%d\n",p.t[i]);
    }
}
 
void enfiler(file *f,char c)
{
    maillon_ptr pt; 
    pt=((maillon*) malloc (sizeof (maillon)));
    pt->val=c;
    pt->lien=NULL;
    if ((f->fin==NULL)&&(f->debut==NULL))
    {
      f->fin=pt;  
      f->debut=pt;
    }
    else 
    {
      f->fin->lien=pt;
      f->fin=pt;
    }
}
 
void file_vide(file*f)
{
    f->fin=NULL;
    f->debut=NULL;
}
 
void afficher_file (file f)
{
    maillon_ptr pt;
    pt=f.debut; int k=1;
    if ((f.fin==NULL)&&(f.debut==NULL))
    printf ("file vide\n");
    else 
    for(pt=f.debut;pt!=NULL;pt=pt->lien)
    {
      printf("la file a %d  element et s'affiche: %c\n",k,pt->val);
      k++; 
    }
}
 
void evaluer (file *f,pile *p)
{
    int a,b,c,s;
    maillon_ptr pt;
    maillon_ptr p1;
 
    for (pt=f->debut;pt!=NULL;pt=pt->lien)
    {
      switch (pt->val)
      {
        case'-':
        {
          b=depiler(p);
          c=depiler(p);
          s=b-c;
          empiler(p,s);
          break;
        }
        case'+':
        {
          b=depiler(p);
          c=depiler(p);
          s=b+c;
          empiler(p,s);
          break;
        }
        case'/':
        {
          b=depiler(p);
          c=depiler(p);
          s=b/c;
          empiler(p,s);
          break;
        }
        case'*':
        {
          b=depiler(p);
          c=depiler(p);
          s=b*c;
          empiler(p,s);
          break;
        }
        default :a=atoi(&f->debut->val);
        empiler(p,a);
        break;
      }
      pt=pt->lien;
    }
    return depiler(p);
}
 
main()
{
    pile p;
    file f;
    file_vide(&f);
    pile_vide(&p); 
    char p_evaluer[20];

Evaluation d'une expression arithmétiqueà partir de sa notation post-fixé (en dev c++

Dev-C++

Vue hybride

Discussions similaires

Partager

Partager