problème construction arbre binaire

Version imprimable

1 pièce(s) jointe(s)

Salut
J'essaye de réaliser un programme en C++ qui évalue une expression mathématique en se
basant sur les arbres binaires.
Exemple :
8-40*20/5+6-63

En premier lieu, je dois construire un arbre comme suit :
(1) En partant de la droite, je détecte le '-', on met à droite le '-' dans la racine
et le '63' sera le fils droit.
(2) pour le fils gauche en répete l'étape (1), et ainsi de suite on obtient l'arbre ci-contre :
Pièce jointe 175958

Les fonctions : "void buildBinaryTreePrivate(string exp , node* pNode);" et "void buildBinaryTree(string exp);" sont concernées
par la construction de l'arbre.

voilà le code :
calc.h :

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
 
#include <string>
#include <iostream>
#include <list>
 
using namespace std;
 
const int nbStatus = 5;
const int nbChars = 16;
const string exprCharset = "0123456789+-*/()";
const int automate [nbStatus][nbChars] = {
    {3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 0, 0, 1, 0},
    {3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 0, 0, 0, 0, 1, 0},
    {3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 5, 5, 5, 5, 0, 4},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 5, 5, 5, 0, 4},
    {3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 0, 0, 0, 0, 1, 0}
  };
 
class simpleCalc
{
 private:
  struct node
  {
    string key;
    node* pLeft;
    node* pRight;
  };
  node* pRoot;
 
 
  void buildBinaryTreePrivate(string exp , node* pNode);
  void bfsPrivate(node* pNode);
  void inOrderPrivate(node* pNode);
 
 
 
 public:
  string expr;
  list<string> file;
 
  simpleCalc(string expr);
  node* init(string key);
  void buildBinaryTree(string exp);
  void charByChar(string exp);
  void bfs(void);
  void inOrder(void);
  bool wellParanthesed(void);
  bool expressionIsValide(void);
};

calc.cpp :

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
137
138
139
140
141
142
143
144
 
#include <iostream>
#include <string>
#include <iterator>
#include <cstdlib>
#include <cctype>
#include <queue>
#include <list>
 
 
#include "calc.h"
 
simpleCalc::simpleCalc(string exprClavier)
{
  expr = exprClavier;
  pRoot = NULL;
}
 
simpleCalc::node* simpleCalc::init(string key)
{
  node* n = new node;
  n->key = key;
  n->pLeft = NULL;
  n->pRight = NULL;
}
 
void simpleCalc::buildBinaryTree(string exp)
{
  buildBinaryTreePrivate(exp,pRoot);
}
 
void simpleCalc::buildBinaryTreePrivate(string exp , node* pNode)
{
   size_t pos = exp.find_last_of("+-*/");
   if (pos != string::npos)
     {
       if (pRoot == NULL)
	 {
	    string leftExpr = exp.substr(0,pos);
	    string rightExpr = exp.substr(pos+1);
	    pRoot = init(exp.substr(pos,1));
	    //cout<<exp.substr(pos,1)<<" ";
	    buildBinaryTreePrivate(rightExpr,pRoot->pRight);
	    buildBinaryTreePrivate(leftExpr,pRoot->pLeft);
	 }
       else
	 {
	    string leftExpr = exp.substr(0,pos);
	    string rightExpr = exp.substr(pos+1);
	    pNode = init(exp.substr(pos,1));
	    //cout<<exp.substr(pos,1)<<" ";
	    buildBinaryTreePrivate(rightExpr,pNode->pRight);
	    buildBinaryTreePrivate(leftExpr,pNode->pLeft);
	 }
     }
   else
     pNode = init(exp);
}
 
void simpleCalc::charByChar(string exp)
{
  size_t pos = exp.find_last_of("+-*/");
   if (pos == string::npos) 
     file.push_back(exp);
   else
     {
      file.push_back(exp.substr(pos,1));
        string leftExpr = exp.substr(0,pos);
	string rightExpr = exp.substr(pos+1);
	charByChar(rightExpr);
	charByChar(leftExpr);
     }
}
 
void simpleCalc::bfs(void)
{
  bfsPrivate(pRoot);
}
 
void simpleCalc::bfsPrivate(node* pNode)
{
  if (pRoot != NULL)
    {
      queue<node*> file;
      file.push(pNode);
      while (!file.empty())
	{
	  node* current = new node;
	  if (current == NULL) return;
	  current = file.front();
	  cout<<current->key<<" ";
	  file.pop();
	  if (current->pLeft != NULL) file.push(current->pLeft);
	  if (current->pRight != NULL) file.push(current->pRight);
	}
    }
  else cout<<"L'arbre est vide.\n";
}
 
 
void simpleCalc::inOrder(void)
{
   inOrderPrivate(pRoot);
}
 
void simpleCalc::inOrderPrivate(node* pNode)
{
if (pRoot != NULL)
    {
      if (pNode->pLeft != NULL) inOrderPrivate(pNode->pLeft);
      cout<<pNode->key<<" ";
      if (pNode->pRight != NULL) inOrderPrivate(pNode->pRight);
    }
  else cout<<"L'arbre est vide.\n";
}
 
 
bool simpleCalc::wellParanthesed()
{ 
  int niveau = 0;
  for (std::string::iterator it = expr.begin() ; it != expr.end() ; ++it)
    {
      if (*it == '(') niveau += 1;
      else if(*it == ')') 
	{
	  niveau -= 1;
	  if (niveau < 0) return false;
	}
    }
  return niveau == 0;
}
 
bool simpleCalc::expressionIsValide()
{
   size_t status = 1;
   std::string::iterator it = expr.begin();
   while (it != expr.end() && status != 0)
    {
      size_t ligne = exprCharset.find(*it);
      status = automate[status-1][ligne];
      it++;
    }
  return wellParanthesed() && (status == 3 || status == 4);
}

main.cpp :

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
 
#include <iostream>
#include <string>
#include <limits>
#include <iterator>
#include <list>
#include <cstdlib>
 
#include "calc.cpp"
 
int main()
{
  string expression;
  cout<<"Donnez l'expression mathématique à évaluer :\n";
  getline(cin,expression);
 
  simpleCalc sc(expression);
 
  if (!sc.expressionIsValide())
    {
      cout<<"Expression non valide.\n";
      return 0;
    }
  sc.buildBinaryTree(sc.expr);
 
  /* sc.charByChar(sc.expr);
  string lastOne = sc.file.back();
  sc.file.pop_back();
  for(list<string>::iterator it = sc.file.begin() ; it != sc.file.end() ; ++it)
    {
        char* end;
	long a =strtol((*it).c_str(),&end,10);
	sc.addNode(*it,*end,false);
    }
  char* end;
  long a =strtol(lastOne.c_str(),&end,10);
  sc.addNode(lastOne,*end,true);*/
 
  sc.bfs();
  cout<<"\n";
  sc.inOrder();
  cout<<"\n";
  return 0;
}

25/04/2015, 03h44
stendhal666

Très beau schéma, merci aussi pour le code mais tu ne dis pas quel est ton problème :)
25/04/2015, 09h44
LandReagan
Salut!

Je crois que je sais... Tu obtiens une erreur de segmentation dans BuiltBinaryTreePrivate parce que tu utilises un pointeur non initialisé: pRoot (d'ailleurs j'adore ce nom, je ne sais pas si tu as fait exprès... :mrgreen:).
Et pRoot (hi hi, je m'en remets pas) n'est pas défini parce que tu as oublié le return dans ta fonction init():
Code:

1 2 3 4 5 6 7 8 9 simpleCalc::node* simpleCalc::init(string key) { node* n = new node; n->key = key; n->pLeft = NULL; n->pRight = NULL; // manque un truc, là... }
25/04/2015, 13h50
jo_link_noir

C'est vraiment une erreur bête, je te conseille d'activer les options du compilateur: -Wall -Wextra à minima pour gcc et clang,

"pRoot" est un pointeur vers la racine. Il est initialisé dans le constructeur :

Code:

1
2
3
4
5
6
 
simpleCalc::simpleCalc(string exprClavier)
{
  expr = exprClavier;
  pRoot = NULL;
}

J'ai corrigé le init :

Code:

1
2
3
4
5
6
7
8
9
 
simpleCalc::node* simpleCalc::init(string key)
{
  node* n = new node;
  n->key = key;
  n->pLeft = NULL;
  n->pRight = NULL;
  return n;
}

Mon problème est la fonction :

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
 
void simpleCalc::buildBinaryTreePrivate(string exp , node* pNode)
{
   size_t pos = exp.find_last_of("+-*/");
   if (pos != string::npos)
     {
       if (pRoot == NULL)
	 {
	    string leftExpr = exp.substr(0,pos);
	    string rightExpr = exp.substr(pos+1);
	    pRoot = init(exp.substr(pos,1));
	    //cout<<exp.substr(pos,1)<<" ";
	    buildBinaryTreePrivate(rightExpr,pRoot->pRight);
	    buildBinaryTreePrivate(leftExpr,pRoot->pLeft);
	 }
       else
	 {
	    string leftExpr = exp.substr(0,pos);
	    string rightExpr = exp.substr(pos+1);
	    pNode = init(exp.substr(pos,1));
	    //cout<<exp.substr(pos,1)<<" ";
	    buildBinaryTreePrivate(rightExpr,pNode->pRight);
	    buildBinaryTreePrivate(leftExpr,pNode->pLeft);
	 }
     }
   else
     pNode = init(exp);
}

elle est appelé par :

Code:

1
2
3
4
5
 
void simpleCalc::buildBinaryTree(string exp)
{
  buildBinaryTreePrivate(exp,pRoot);
}

L'algorithme de la fonction est incorrcte, parce que l'arbre n'est pas construit, voilà ce qu'elle donne :

Citation:

$ g++ -Wall -Wextra -std=c++11 main.cpp -o myCalc
$ ./myCalc
Donnez l'expression mathématique à évaluer :
8+4-5

parcours BFS :
-

parcours in order (infixe) :
-
$

la fonction "buildBinaryTreePrivate" construit uniquement la racine et pas les autres !

25/04/2015, 20h05
cyprien lekoue

Salut toi!!!!! quel est ton véritable problème ????
25/04/2015, 20h32
blackbird1

Mon problème est que je ne vois pas comment implémenter correctement la fonction "buildBinaryTreePrivate". Merci
26/04/2015, 01h07
SaBe94

Tu dois passer par référence le pointeur de ta fonction buildBinaryTreePrivate.

Code:

void simpleCalc::buildBinaryTreePrivate(string exp , node*& pNode)
26/04/2015, 09h14
LandReagan

Citation:

Envoyé par SaBe94

Tu dois passer par référence le pointeur de ta fonction buildBinaryTreePrivate.

Passer un pointeur par référence, hein... :roll:

Bon, sans rire, du coup j'ai regardé un petit peu plus ton code et je n'ai remarqué qu'un seul opérateur "new", uniquement utilisé à la construction de simpleCalc, c'est à dire une seule fois dans ton application. Il ne peut donc y avoir qu'un seul node à la fin.

Ainsi, lorsque buildBinaryTree appelle buildBinaryTreePrivate, ça "marche" puisque comme tu as dit pRoot est initialisé, par contre lors de tous tes appels réccursifs suivants tout se fait dans le vent.
Il faudrait donc allouer de la mémoire à pRight et pLeft à un moment ou à un autre (au bon moment, en fait).
26/04/2015, 10h43
SaBe94

Citation:

Envoyé par LandReagan

Passer un pointeur par référence, hein... :roll:

Bon, sans rire, du coup j'ai regardé un petit peu plus ton code et je n'ai remarqué qu'un seul opérateur "new", uniquement utilisé à la construction de simpleCalc, c'est à dire une seule fois dans ton application. Il ne peut donc y avoir qu'un seul node à la fin.

Ainsi, lorsque buildBinaryTree appelle buildBinaryTreePrivate, ça "marche" puisque comme tu as dit pRoot est initialisé, par contre lors de tous tes appels réccursifs suivants tout se fait dans le vent.
Il faudrait donc allouer de la mémoire à pRight et pLeft à un moment ou à un autre (au bon moment, en fait).

Ce n'est peut être pas très esthétique mais c'est la solution à son problème. A moins que tu ne saches pas que cela existe dans ce cas une simple recherche google te renseignera.

Les news sont fait de façon récursive avec la méthode init lors de l'appel de buildBinaryTreePrivate. Le problème c'est qu'il passe par copie un pointeur non initialisé en paramètre. Il faut garder une référence sur le pointeur donc ou bien passer le pointeur par référence ou bien passer par des doubles pointeurs.
26/04/2015, 12h21
blackbird1

1 pièce(s) jointe(s)

l'allocation est bien faite à chaque appel récursif.

exemple d'éxécution à la main :
"8+4-5"
1er appel : buildBinaryTreePrivate("8+4-5",pRoot);
pRoot == NULL
leftExpr = "5"
rightExpr = "8+4"
construction de la racine : Root = init("-");

2eme appel :
buildBinaryTreePrivate("5",pRoot->pRight);
pos == string::npos
donc pNode = init("5"); normalement pNode est pRoot->pRight

3eme appel :
buildBinaryTreePrivate("8+4",pRoot->pLeft);
pos != string::npos
donc :
leftExpr = "8"
rightExpr = "4"
pNode = init(exp.substr(pos,1)); donne pRoot->pLeft = init("+");

4eme appel :
buildBinaryTreePrivate("4",pNode->pRight); ==> buildBinaryTreePrivate("4",pRoot->pLeft ->pRight);
pos == string::npos
donc pNode = init("4"); normalement pRoot->pLeft ->pRight = init("4");

5eme appel :
buildBinaryTreePrivate("8",pNode->pLeft); ==> buildBinaryTreePrivate("8",pRoot->pLeft ->pLeft);
pos == string::npos
donc pNode = init("8"); normalement pRoot->pLeft ->pLeft = init("8");

fin

Mon premier souci est la construction de l'arbre. L'arbre construit est fausse parce que elle ne prend pas en considération la priorité des opérateurs et les parenthèses.

pour l'exemple : 8 - 40 * 20 / 5 + 6 - 63, l'arbre est donc :
Pièce jointe 176052

Le parcours postfixe donne : 8 40 20 * 5 / - 6 + 63 -
26/04/2015, 12h32
SaBe94

T'as fait la modif que j'ai indiquée ?

Si je teste chez moi ça me donne :

Citation:

Envoyé par CMD

Donnez l'expression mathématique à évaluer :
8+4-5
- + 5 8 4
8 + 4 - 5
26/04/2015, 13h01
blackbird1

1) ça marche bien en référençant le pointeur !!! (Merci SaBe94)
Mais je ne vois pas la cause.

2) Le programme fonctionne bien avec des opérateurs du même priorité et sans parenthèse.
Comment le généralisé ?
26/04/2015, 13h31
SaBe94
Citation:

Envoyé par blackbird1

1) ça marche bien en référençant le pointeur !!! (Merci SaBe94)
Mais je ne vois pas la cause.

L'initialisation de pRoot marche. Mais, quand tu appelles sur ses noeuds enfants buildBinaryTreePrivate
Code:

1 2 3 node* pNode = pNode->pChild; buildBinaryTreePrivate( expr, pNode );
Tu passes pNode en copiant le pointeur.

Ce qui veut dire que dans la fonction appelé tu as bien
Code:

1 2 3 4 pNodeAppelé = NULL //Mais les adresses stockant les pointeurs sont différentes &pNodeAppelé != &pNode
En fait, en allouant pNodeAppelé tu alloues bien un Node mais qui n'a aucun lien avec pRoot.
Pour garder ce lien tu dois t'assurer que :
Code:

1 2 &pNodeAppelé == &pNode == &(pROOT->pChild)
Une des façons de faire est de passer les arguments par référence.

C'est un problème fréquent quand on effectue les allocations dans les fonctions appelés.
C'est pourquoi généralement on essaie de faire toutes les allocations par les appelants. Cela permet aussi d'éviter les fuites mémoires.

Citation:

Envoyé par blackbird1

2) Le programme fonctionne bien avec des opérateurs du même priorité et sans parenthèse.
Comment le généralisé ?

C'est un problème de grammaire formelle et ce n'est pas mon fort :(...
Je te conseille de chercher des ressources sur les expressions régulières en arithmétique.
27/04/2015, 10h00
Bousk

Citation:

Envoyé par blackbird1

1) ça marche bien en référençant le pointeur !!! (Merci SaBe94)
Mais je ne vois pas la cause.

Point de magie. En C++ les paramètres sont passés par copie, sauf la référence. Un pointeur n'est pas plus exceptionnel qu'un int et passera aussi par copie.
L'objet pointé ne change pas, mais si tu modifies ton pointeur, tu modifies sa copie.