Probleme conversion expression en arbre binaire
Bonjour, je sollicite de l'aide dans le but de résoudre un exercice de programmation en C que j'ai à faire.
Je écrire un programme qui convertit une expression infixée (a+b) en expression préfixée ( +ab) à l'aide d'un arbre binaire. J'ai réussie a écrire un programme que je trouve correct qui compile sans erreur. Cependant, à l'exécution il y a une erreur de segmentation et le debugger m'indique une erreur sur ma fonction d'affichage qui marche (testé avec un arbre :? ). Donc il doit y avoir un problème avec au niveau de la construction de l'arbre que je n'arrive pas à déceler.
Je mets le code de mon programme à la suite du post en espérant que quelqu'un puisse m'aider. Merci d'avance !!!
Code:
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
|
#include <stdio.h>
#include <stdlib.h>
struct noeud{ // Noeud et feuille de l'arbre binaire
char valeur;
struct noeud *droite;
struct noeud *gauche;
};
typedef struct noeud Arbre;
int empiler(Arbre *haut, char donnee);
int depiler(Arbre *haut);
void lier(Arbre *Op, Arbre *Nb);
void Prefixe(Arbre *racine);
int trier(char donnee,Arbre *top, Arbre *haut);
int main(){
char c;
Arbre *haut=malloc(sizeof(Arbre));//Haut de la pile des operandes
haut->droite=NULL;
haut->gauche=NULL;
Arbre *top=malloc(sizeof(Arbre));// Haut de la pile des operateurs
top->droite=NULL;
top->gauche=NULL;
while((c=getchar())!='\n'){
trier(c,top->droite,haut->droite);
}
Prefixe(haut->gauche);
return 0;
}
int empiler(Arbre *haut, char donnee){ // empiler un element de type Arbre
Arbre *nouveau;
if ((nouveau=(Arbre*)malloc(sizeof(Arbre)))== NULL) return -1;
nouveau->valeur=donnee;
nouveau->droite=haut;
nouveau->gauche=NULL;
haut=nouveau;
return 0;
}
int depiler(Arbre *haut){ // depiler un element de type Arbre
if(haut==NULL)
return -1;
Arbre *temporaire=haut;
haut=haut->droite;
temporaire->droite=NULL;
temporaire->gauche=NULL;
return 0;
}
void lier(Arbre *Op, Arbre *Nb) // fonction qui construit l'arbre avec les operateurs et operandes empiles grace a trier
{
if(Op->valeur=='(') depiler(Op);
Arbre *racine=malloc(sizeof(Arbre));
if(Nb->gauche==NULL){
racine->gauche=Op;
racine->droite=Nb;
Op=Op->droite;
Nb->gauche=racine->gauche;
racine->gauche->gauche=Nb->droite;
depiler(Nb->droite);
racine->gauche->droite=Nb->droite;
depiler(Nb->droite);
}
else{
racine->gauche=Op;
Op=Op->droite;
racine->droite=Nb->gauche;
Nb->gauche=racine->gauche;
racine->gauche->gauche=racine->droite;
racine->gauche->droite=Nb->droite;
depiler(Nb->droite);
}
}
void Prefixe(Arbre *racine){ // affiche l'arbre en notation prefixe
printf("%c",racine->valeur);
if(racine->gauche!=NULL) Prefixe(racine->gauche);
if(racine->droite!=NULL) Prefixe(racine->droite);
}
int trier(char donnee,Arbre *top, Arbre *haut){
if (donnee=='('){
empiler(top,donnee);
}
else if(donnee!='+'&& donnee!='-' && donnee!='*' && donnee!='/'){
empiler(haut,donnee);
}
else if(donnee=='+' || donnee=='-' || donnee=='*' || donnee=='/'){
if ((top==NULL) || (top->valeur=='(') || top->valeur=='+'|| top->valeur=='-'||((top->valeur=='*'||top->valeur=='/')&&(donnee=='*'||donnee=='/'))){
empiler(top,donnee);
}
else{
do{
lier(top,haut);//connecter les noeuds
}
while((top->droite!=NULL) || (top->droite->valeur!='(') || ((top->valeur=='*'||top->valeur=='/')&&(donnee=='+'||donnee=='-')));
empiler(haut,donnee);
}
}
else if (donnee==')'){
while (top->valeur!='('){
lier(top,haut);
}
}
else{
printf("Erreur!!");
return -1;
}
while(top!=NULL){
lier(top,haut);
}
return 0;
} |
