Probleme conversion expression en arbre binaire

**seline** · 14/11/2010, 18h55

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 :

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
 
 
 
#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;
}

**diogene** · 15/11/2010, 14h27

1-

Code :

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

if((Op->droite=='(' || Op->droite==')') depiler(Op);

- Manque une parenthèses ) ou une parenthèse ( en trop
- Op->droite est un pointeur struct noeud * et ne peut être comparé à un int.
Ces deux erreurs ont certainement été signalées par le compilateur.

2- Plus grave sur le principe : Les fonctions empiler()/depiler() ne peuvent pas fonctionner : tu modifies haut dans ces fonctions, mais haut est une variable locale et c'est la variable locale qui est modifiée, la variable utilisée pour l'appel des fonctions ne change pas. Idem pour lier() et la variable Op

**seline** · 15/11/2010, 19h34

Envoyé par diogene

1-

Code :

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

if((Op->droite=='(' || Op->droite==')') depiler(Op);

- Manque une parenthèses ) ou une parenthèse ( en trop
- Op->droite est un pointeur struct noeud * et ne peut être comparé à un int.
Ces deux erreurs ont certainement été signalées par le compilateur.

2- Plus grave sur le principe : Les fonctions empiler()/depiler() ne peuvent pas fonctionner : tu modifies haut dans ces fonctions, mais haut est une variable locale et c'est la variable locale qui est modifiée, la variable utilisée pour l'appel des fonctions ne change pas. Idem pour lier() et la variable Op

Merci pour votre réponse, en effet je me suis trompé pour les parathèses et j'ai corriger le tire.

Cependant avec mes fonctions empiler() / depiler(), sauf erreur de ma part, manipule le haut de la fonction main par l'intermédiaire d'un pointeur.

**diogene** · 15/11/2010, 20h07

Cependant avec mes fonctions empiler() / depiler(), sauf erreur de ma part, manipule le haut de la fonction main par l'intermédiaire d'un pointeur.

Non, tu manipules une copie.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
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; // ne sert à rien : haut sera détruit en sortie de fonction
  return 0;
}

Par exemple, l'appel :

Code :

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

1
2
3
haut = NULL;
empiler(haut, ....); 
//haut n'a pas changé et vaut toujours NULL

**seline** · 15/11/2010, 21h04

Merci diogène, je vois de quoi tu veux parler. Mais dans ce cas, n'y a t il aucun moyen de manipuler directement ces variables?

Puisque bon ,j'ai vu sur divers sites comment les piles fonctionne et j'ai éssayé de l'adapter à ma structure Arbre.

**diogene** · 15/11/2010, 22h11

Mais dans ce cas, n'y a t il aucun moyen de manipuler directement ces variables?

Il faut passer leur adresse.

Ce qui donnerait dans l'exemple :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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; // ne sert à rien : haut sera détruit en sortie de fonction
  return 0;
}
.....
haut = NULL;
empiler(&haut, ....);

**seline** · 16/11/2010, 18h28

Ça n'a pas l'air de marché

, je vais y travaillé de plus ardument et éssayé de le faire fonctionner.

Probleme conversion expression en arbre binaire

C

Discussions similaires

Partager

Partager