probleme avec une "structure en arbre"

**kamouminator** · 07/11/2006, 21h15

voila,
toujours en rapport avec ma calculatrice,

j'essaye maintenant de gerer les parentheses,
pour ce faire, je demande a mon programme de créer un nouvelle liste chainée a chaque fois que j'appuie sur '(' et revenir a la liste precedente a chaque fois que j'appuie sur ')'

un exemple (tres grossierement):

2+(4*(3+5))+5

donnerai: 2 + nouvelleListe + 5
nouvelleListe = 4 * nouvelleListe 2
nouelleListe2 = 3 + 5

j'ai joint a ce post un diagramme explicant cela plus en detail...

pour l'ainstant le programe pour l'exemple cité plus haut devrai me sortir a l'ecran: le nombre 2, le code ascii de +, le nombre 0, le code ascii de + et enfin le nombre 5

or il ne m'affiche que les trois premiers (j'ai l'impression qu'il n'arrive pas a revenir au niveau inferieur)

et bizarement il ne me fais pas cette erreure lorsqu'il n'y a q'un "niveau" de parentheses: 3 + (4+2)+6
affichera bien: le nombre 3, le code ascii de +, le nombre 0, le code ascii de + et enfin le nombre 6

la fonction qui s'occupe de gerer les parentheses est Kscanf()

voila le code de ma calculete:

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
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
#include <stdio.h>
#include<stdlib.h>
#include <conio.h>
#include<math.h>
 
#define number 0
#define add 1
#define sub 2
#define mult 3
#define divi 4
#define open 5
#define close 6
#define point 7
 
 
#define inconnu -1
 
 
struct elem
{
    double value; //ici sera stocké soit le code ascii d'un operande soit la valeur d'un nombre
    int type; //type de l'element : nombre, operande, parenthese...
    struct elem *prev; //pointeur vers l'element precedent
    struct elem *next; //pointeur vers l'element suivant
    struct string * sup;
    struct string * inf;
};
 
 
 
/*structure contenant un pointeur sur le debut de la liste et un autre sur la fin*/
struct string
{
    struct elem *first;
    struct elem *last;
    struct elem * inf;
};
 
 
/******************************************************************************/
/*fonction initialisation d'une liste*/
void Init(struct string * l)
{
 
    l->first = NULL;
    l->last = NULL;
 
 
}
 
struct string Create_sup_String()
{
    struct string l;
    l.first = NULL;
    l.last = NULL;
    l.inf = NULL;
 
    return l;
 
}
 
 
 
/******************************************************************************/
 
 
/* fonction permettan de rajouter un element en fin de liste*/
void PushBack(struct string *l, double val,int type)
{
    struct elem *nouv = (struct elem*)malloc(sizeof( struct elem));
    if(!nouv)
        return;
    nouv->value = val;
    nouv->type=type;
    nouv->prev = l->last;
    nouv->next = NULL;
    if(l->last)
        l->last->next = nouv;
    else
        l->first = nouv;
    l->last = nouv;
}
/******************************************************************************/
/*fonction permettant de rajouter un element au debut de la liste*/
void PushFront( struct string *l, double val,int type)
{
    struct elem *nouv = ( struct elem*)malloc(sizeof( struct elem));
    if(!nouv)
        return;
    nouv->value = val;
    nouv->type=type;
    nouv->sup=NULL;
    nouv->inf = l;
    nouv->next = l->first;
    nouv->prev = NULL;
    if(l->first)
        l->first->prev = nouv;
    else
        l->last = nouv;
    l->first = nouv;
}
 
void PushFront_NewStruct( struct string *l, double val,int type, struct string * sup)
{
    struct elem *nouv = ( struct elem*)malloc(sizeof( struct elem));
    if(!nouv)
        return;
    nouv->value = val;
    nouv->type=type;
    nouv->sup=sup;
    nouv->inf = l;
    nouv->next = l->first;
    nouv->prev = NULL;
    if(l->first)
        l->first->prev = nouv;
    else
        l->last = nouv;
    l->first = nouv;
    sup->inf=nouv;
}
 
/******************************************************************************/
 
/* Fonction qui teste chaque caractere et renvoie son type */
int get_type(int a)
{
 
    if (a>=48 && a<=57)
        return number;
    if (a==43)
        return add;
    if (a==45)
        return sub;
    if (a==42)
        return mult;
    if (a==47)
        return divi;
    if (a==40 || a==91)
        return open;
    if (a==41 || a==93)
        return close;
    if (a==46)
        return point;
    return inconnu;
 
 
}
/******************************************************************************/
 
/*fonction "imitant" le scanf, a chaque fois qu'on tape un caractere, il sera rajouté a la liste*/
int Kscanf(struct string * l)
{
    int err;
    int a=0;
    int type;
    int nb_p_g=0, nb_p_d=0; //resp nombre ouvertue, nombre fermeture de parentheses
    struct string * en_cours = l; //chaine en cours d'ecriture
    struct string New_string;
    while (a != 13)
    {
        a = getch(); //on copie le code ascii du caractere dans a
        printf("%c",a); //on l'affiche
        type = get_type(a); //on evalue son type
 
        if (a==40) // si '(':ouverture
        {
            nb_p_g++;
            New_string=Create_sup_String();
            PushFront_NewStruct(en_cours,0,open,&New_string); //on crée un element pointant vers une nouvelle structure
            en_cours=&New_string; //on passe au niveau superieur
        }
 
        if (a==41 && en_cours->inf!=NULL) //si ')':fermeture
        {
            nb_p_f++;
            en_cours=en_cours->inf->inf; //on reviens au niveau inverieure
 
        }
 
        //if (a== || a==)err=ERROR_FORBIDEN_CHARS;
 
        if(a!=13 && a!=40 && a!=41 )
            PushFront(en_cours,a,type); //on rajoute un element a la pile contenant: la valeur, et le type du caractere
    }
    //if (nb_p_g>nb_pd)
    //err=ERROR_TOO_MUCH_OPEN;
 
    //if (nb_p_g<nb_pd)
    // err=ERROR_TOO_MUCH_CLOSE;
 
 
    return err;
 
}
/******************************************************************************/
/*fonction affichant le contenu de la liste*/
void View(struct string l)
{
    //printf("\n");
    struct elem *pelem = l.first;
    while(pelem)
    {
        int popo=3;
        printf("%.*f type=%d\n",popo,pelem->value,pelem->type);
        pelem = pelem->next;
    }
}
 
/******************************************************************************/
 
void detect_nb_flottant(struct string * l)
{
 
    double nb_tmp=0.;
    int i=0;
    struct elem *pelem = l->first;
    struct elem *point_droite;
 
    struct elem *point_gauche;
    /*d'abord chercher les nombre a virgule*/
 
    while(pelem!=NULL )
    {
 
        if (pelem->type == point)
        {
            point_droite=pelem->prev;
            point_gauche=pelem->next;
 
            while(point_gauche !=NULL && point_gauche->type == number)
            {
 
                nb_tmp=nb_tmp+(((point_gauche->value)-48)*pow(10,i));
                i++;
 
                if(point_gauche->next ==NULL)
                {
                    pelem->next=point_gauche->next;
                    l->last=pelem;
                    break;
                }
                if (point_gauche->next !=NULL)
                {
                    point_gauche = point_gauche->next;
                    free(pelem->next);
                    pelem->next=point_gauche;
                    pelem->next->prev=pelem;
                }
 
            }//int §=0;
 
            i=-1;
 
 
            while(point_droite !=NULL && point_droite->type == number)
            {
 
 
                nb_tmp=nb_tmp+(((point_droite->value)-48)*pow(10,i));
                i--;
 
                if(point_droite->prev ==NULL)
                {
                    pelem->prev=point_droite->prev;
                    l->first=pelem;
                    break;
 
                }
                if(point_droite->prev !=NULL)
                {
                    point_droite = point_droite->prev;
                    free(pelem->prev);
                    pelem->prev=point_droite;
                    pelem->prev->next=pelem;
                }
 
 
            }
 
 
            pelem->value=nb_tmp+48;
            pelem->type=number;
 
 
        }
        i=0;
        nb_tmp=0;
        pelem = pelem->next;
 
 
 
    }
 
 
}
 
 
 
/******************************************************************************/
 
 
void stock_nb(struct string l,struct string * nb)
{
 
 
    double nb_tmp=0.;
    int i=0;
    struct elem *pelem = l.first;
    /*d'abord chercher les nombre a virgule*/
 
    detect_nb_flottant(&l);
    pelem = l.first;
 
 
    while(pelem!=NULL) //tant qu l'element n'est pas NULL (fin de liste)
 
 
    {
 
 
 
 
 
 
        if (pelem->type == number)
        {
 
            while(pelem !=NULL && pelem->type==number)
            {
 
 
                nb_tmp=nb_tmp+(((pelem->value)-48)*pow(10,i));           // lorsqu'on li les unité i =0, les disaines i=1, les centaines i=2
 
 
                // on a donc a la fin nb_tmp= unité + 10 * dizaine + 100*centaine...
                i++;
 
                pelem = pelem->next; //la lecture se fais de droite a gauche pour pouvoir d'abord avoir les unité puis les dizaines puis les centaines etc...
            }
 
 
 
            PushFront(nb,nb_tmp,0);// quand le caractere lu n'est plus un chiffre, on rajoute nb_tmp a la nouvelle liste
            i=0;
            nb_tmp=0;
        }
 
 
        if (pelem !=NULL && pelem->type != 0)
        {
            PushFront(nb,pelem->value,pelem->type); //quand le caractere lu n'est pas un chiffre, on le copie directement dans un nouvel element de la liste
 
            pelem = pelem->next;
 
        }
 
 
 
    }
 
 
 
}
 
 
 
/******************************************************************************/
 
 
int main()
{
 
    struct string  l;
    struct string nb;
    Init(&l);
    Init(&nb);
    printf(">");
    Kscanf(&l);
    printf("\n");
    //View(l);
    stock_nb(l, &nb);
    printf(">>");
    View(nb);
    //char tab[10];
    //scanf("%s",tab);
 
    return 0;
}

**kamouminator** · 07/11/2006, 22h21

petit sur le fonctionnement de mon programme:

chaque caractére entré par l'utilisateur est stocké dans un element d'une liste.

comme di precedement, a chaque appuie de '(' un element pointant sur une vouvelle liste est créé.

on rempli donc la liste superieure.

si '(' on crée encore un niveau sup, etc...

si ')' don redescend a la liste inferieure

ensuite la fonction stock_nb va convertir tous les caracteres represantant de chiffres en nombre ! ex:
les caractere '1' '2' '3' seront converti en: 123

voila, si vous avez besoin de plus de precision je suis la pour ca...

probleme avec une "structure en arbre"

C

Discussions similaires

Partager

Partager