Arbre syntaxique [code assez long]

**line86** · 15/05/2007, 20h58

Bonsoir a vous,
Voila je dois creer un arbre syntaxique a partir d'une notation polonaise inverse, c'est a dire donné l'expression equivalente en notation habituelle(infixe).
Mais je rencontre des difficultées avec la fonction ArbreSyntax.
Merci pour votre aide

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>
 
typedef struct abr
{
 char op;
 union
  {
   int valeur;
   struct
    {
     struct abr* FilsG;
     struct abr* FilsD;
    };
  };
}Arbre;
 
 
typedef struct pile {
  Arbre* valeur;
  struct pile *next;
} Pile;
 
 
Pile* stack = NULL;
 
Pile *InitialisePile(Arbre* val,Pile *next)
{
 Pile *p = (Pile *)malloc(sizeof(Pile));
 if ( p == NULL) {
   fprintf(stderr,"Plus de memoire\n");
   exit(-1);
 }
 p->valeur = val;
 p->next = next;
 return p;
}
 
Arbre* depiler(void) /* return un arbre */
{
 if (stack == NULL) {
   fprintf(stderr,"Tentative de depiler une pile vide\n");
   exit(-1);
 }
 Arbre* r = stack->valeur;
 Pile* tmp = stack;
 stack = stack->next;
 free(tmp);
 return r;
}
 
void empiler(Arbre* i) /* retourne une pile */
{
 stack = InitialisePile(i,stack);
}
 
/* ARBRE */
Arbre* CreerNoeud(char operateur)
{
 Arbre* a=(Arbre*) malloc (sizeof(Arbre));
 if (NULL == a) 
  {
   fprintf(stderr,"Erreur d'allocation(CreerNoeud)"); 
   exit(1);
  }
 a->op = operateur;
 a->FilsG = a->FilsD = NULL;
 return a;
}
 
Arbre* CreerFeuille(int val)
{
  Arbre* a=(Arbre*) malloc (sizeof(Arbre));
 if (NULL == a) 
  {
   fprintf(stderr,"Erreur d'allocation(CreerFeuille)"); 
   exit(1);
  }
 a->valeur = val;
 return a;
}
 
void AffichageInfixe(Arbre* a)
{
 while (a)
  {
   AffichageInfixe(a->FilsG);
   printf ("%d ",a->valeur);
   AffichageInfixe(a->FilsD);
  }
}
 
int EstOperateur (char *ch,int *pos, int *nbr, char *op)
{
 while(ch[*pos]== ' ') 
  (*pos)++;
 if(ch[*pos]=='\0') 
  return -1;
 /* Pour traiter les operateurs */
 if(ch[*pos]=='+'|| ch[*pos]=='-'|| ch[*pos]=='*' || ch[*pos]=='/')
  {*op=ch[*pos];
   (*pos)++;
   return 1;
  }
 /* Cas ou on a les chiffres */
 *nbr=0;
 while (ch[*pos]>='0' && ch[*pos]<='9')
   {*nbr=(*nbr)*10+ch[*pos]-'0';
    (*pos)++;
   }
 return 0;
}
 
int ArbreSyntax (char *sh, int *valeur)
{
 int val;
 Arbre *arg, *arg1, *arg2, *arg3;
 int pos = 0;
 char op;
 int nombre;
 do
   {
    val = EstOperateur (sh, &pos, &nombre, &op);
    printf ("val=%d\n", val);
 
    if (val == 0)/* les chiffres */
      {
       arg = CreerFeuille(val);
       empiler(arg);
       printf ("empile nombre=%d\n", arg->valeur);
      }
    if (val == 1)
      {
       switch (op)
	 {
	 case '+':
	  arg1=depiler(); arg2=depiler();
	  arg3->FilsG=arg1; arg3->FilsD=arg2;
	  empiler (arg3);
	  break;
         default : printf("Erreur dans les signes");
         }
	/* case '-':
	  val3 = val1 - val2;
	  break;
 
	 case '*':
	  val3 = val1 * val2;
	  break;
 
	 case '/':
	  val3 = val1 / val2;
	  break;
 
 
       if (!Empiler (&P, val3))
	return 0;*/
      }
    printf ("\n");
   } while (val != -1);
 return 0;
}
 
int main (void)
{
 int valeur;
 char texte[150];
 gets (texte);
 Arbre *a;
 ArbreSyntax (texte, &valeur);
 printf ("L'affichage de l'arbre syntaxique est:\n");
 AffichageInfixe (a);
 return 0;
}

**LinuxUser** · 15/05/2007, 21h56

Je n'ai pas lu tout ton code, mais je te conseil d'effectuer quelques chagement, et d'expliquer precisement ce qui te pose problème.

Tout d'abord :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
typedef struct abr
{
 char op;
 union
  {
   int valeur;
   struct    // nom de la structure 
    {
     struct abr* FilsG;
     struct abr* FilsD;
    }/* ou ici */;
  };
}Arbre;

Ensuite :

Code :

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

1
2
3
4
5
 
void empiler(Arbre* i) /* retourne une pile */
{
 stack = InitialisePile(i,stack);
}

Alors qu'empiler est censé ne rien retourner.

Code :

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

1
2
 
if (NULL == a) // test si NULL = a

Je ne sais pas si ça passe à la compilation, mais c'est assez génant comme test. Et surtout ça na pas de sens il me semble de tester NULL au lieu de a.

**Médinoc** · 16/05/2007, 09h29

Je ne sais pas trop pour le début, mais concernant la dernière remarque: Le test if(NULL == a) est parfaitement valide, et a l'avantage de devenir invalide si on oublie le second '='.
C'est donc en fait, une méthode préconisée (même si je ne la suis pas

).

**diogene** · 16/05/2007, 15h38

Mais je rencontre des difficultées avec la fonction ArbreSyntax

- une erreur et surtout un oubli (les deux en gras rouge) dans cette fonction

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
int ArbreSyntax (char *sh, int *valeur)
{
 int val;
 Arbre *arg, *arg1, *arg2, *arg3;
 int pos = 0;
 char op;
 int nombre;
 do
   {
    val = EstOperateur (sh, &pos, &nombre, &op);
    printf ("val=%d\n", val);

    if (val == 0)/* les chiffres */
      {
       arg = CreerFeuille(nombre);
       empiler(arg);
       printf ("empile nombre=%d\n", arg->valeur);
      }
    if (val == 1)
      {
       switch (op)
	 {
	 case '+':
	  arg1=depiler(); arg2=depiler();
          arg3 = CreerNoeud('+');
	  arg3->FilsG=arg1; arg3->FilsD=arg2;
	  empiler (arg3);
	  break;
.....

- une erreur dans main :

Code :

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

AffichageInfixe (stack->valeur );

- AffichageInfixe ne peut pas marcher : on ne peut savoir si a est un noeud ou une feuille et le test à NULL des pointeurs FilsG et FilsD ne peut marcher puisqu'ils partagent par l'union la même zone mémoire que valeur.
Pour discriminer l'union, on peut utiliser par exemple le champ op en le mettant à ' ' dans le cas d'une feuille :

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
Arbre* CreerFeuille(int val)
{
  Arbre* a=(Arbre*) malloc (sizeof(Arbre));
....
  a->op = ' ';
  a->valeur = val;
 return a;
}
void AffichageInfixe(Arbre* a)
{
 if (a)
    if(a->op == ' ') printf ("%d ",a->valeur);
    else
    {
      AffichageInfixe(a->FilsG);
      printf ("%c ",a->op);
      AffichageInfixe(a->FilsD);
    }
}

**line86** · 17/05/2007, 16h58

Bonjour a vous tous

Je vous remercie pour vos reponses !!!
Je reposte mon code qui fonctionne grace, principalement, a diogene.

Merci bonne journée

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
#include <stdio.h>
#include <stdlib.h>
 
typedef struct abr
{
 char op;
 union
  {
   int valeur;
   struct
    {
     struct abr* FilsG;
     struct abr* FilsD;
    };
  };
}Arbre;
 
 
typedef struct pile {
  Arbre* valeur;
  struct pile *next;
} Pile;
 
 
Pile* stack = NULL;
 
Pile *InitialisePile(Arbre* val,Pile *next)
{
 Pile *p = (Pile *)malloc(sizeof(Pile));
 if ( p == NULL) {
   fprintf(stderr,"Plus de memoire\n");
   exit(-1);
 }
 p->valeur = val;
 p->next = next;
 return p;
}
 
Arbre* depiler(void) /* return un arbre */
{
 if (stack == NULL) {
   fprintf(stderr,"Tentative de depiler une pile vide\n");
   exit(-1);
 }
 Arbre* r = stack->valeur;
 Pile* tmp = stack;
 stack = stack->next;
 free(tmp);
 return r;
}
 
void empiler(Arbre* i) /* retourne une pile */
{
 stack = InitialisePile(i,stack);
}
 
/* ARBRE */
Arbre* CreerNoeud(char operateur)
{
 Arbre* a=(Arbre*) malloc (sizeof(Arbre));
 if (NULL == a) 
  {
   fprintf(stderr,"Erreur d'allocation(CreerNoeud)"); 
   exit(1);
  }
 a->op = operateur;
 a->FilsG = a->FilsD = NULL;
 return a;
}
 
Arbre* CreerFeuille(int val)
{
  Arbre* a=(Arbre*) malloc (sizeof(Arbre));
 if (NULL == a) 
  {
   fprintf(stderr,"Erreur d'allocation(CreerFeuille)"); 
   exit(1);
  }
 a->op = ' ';
 a->valeur = val;
 return a;
}
 
void AffichageInfixe(Arbre* a)
{
 if (a)
   {
    if(a->op == ' ') printf ("%d ",a->valeur);
    else
    {
      if ()
      AffichageInfixe(a->FilsG);
      printf ("%c ",a->op);
      AffichageInfixe(a->FilsD);
    }
   }
}
 
int EstOperateur (char *ch,int *pos, int *nbr, char *op)
{
 while(ch[*pos]== ' ') 
  (*pos)++;
 if(ch[*pos]=='\0') 
  return -1;
 /* Pour traiter les operateurs */
 if(ch[*pos]=='+'|| ch[*pos]=='-'|| ch[*pos]=='*' || ch[*pos]=='/')
  {*op=ch[*pos];
   (*pos)++;
   return 1;
  }
 /* Cas ou on a les chiffres */
 *nbr=0;
 while (ch[*pos]>='0' && ch[*pos]<='9')
   {*nbr=(*nbr)*10+ch[*pos]-'0';
    (*pos)++;
   }
 return 0;
}
 
int ArbreSyntax (char *sh, int *valeur)
{
 int val;
 Arbre *arg, *arg1, *arg2, *arg3;
 int pos = 0;
 char op;
 int nombre;
 do
   {
    val = EstOperateur (sh, &pos, &nombre, &op);
    printf ("val=%d\n", val);
 
    if (val == 0)/* les chiffres */
      {
       arg = CreerFeuille(nombre);
       empiler(arg);
       printf ("empile nombre=%d\n", arg->valeur);
      }
    if (val == 1)
      {
       switch (op)
	 {
	  case '+':
	   arg1=depiler(); arg2=depiler();
           arg3 = CreerNoeud('+');
	   arg3->FilsG=arg1; arg3->FilsD=arg2;
	   empiler (arg3);
	   break;
 
	  case '-':	
           arg1=depiler(); arg2=depiler();
           arg3 = CreerNoeud('-');
	   arg3->FilsG=arg1; arg3->FilsD=arg2;
	   empiler (arg3);
	   break;
 
	  case '*':
	   arg1=depiler(); arg2=depiler();
           arg3 = CreerNoeud('*');
	   arg3->FilsG=arg1; arg3->FilsD=arg2;
	   empiler (arg3);
	   break;
 
	  case '/':
	   arg1=depiler(); arg2=depiler();
           arg3 = CreerNoeud('/');
	   arg3->FilsG=arg1; arg3->FilsD=arg2;
	   empiler (arg3);
	   break;
 
          default : printf("Erreur dans les signes");
         }
      }
    printf ("\n");
 } while (val != -1);
 return 0;
}
 
int main (void)
{
 int valeur;
 char texte[150];
 gets (texte);
 ArbreSyntax (texte, &valeur);
 printf ("L'affichage de l'arbre syntaxique est:\n");
 AffichageInfixe (stack->valeur);
 printf("\n");
 return 0;
}

Arbre syntaxique [code assez long]

C

Vue hybride

Discussions similaires

Partager

Partager