problème construction arbre binaire

**blackbird1** · 25/04/2015, 00h56

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 :
Nom : image.jpg
Affichages : 290
Taille : 20,4 Ko

Nom : image.jpg
Affichages : 290
Taille : 20,4 Ko

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 :

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
 
#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 :

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
 
#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 :

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

**stendhal666** · 25/04/2015, 03h44

Très beau schéma, merci aussi pour le code mais tu ne dis pas quel est ton problème

**LandReagan** · 25/04/2015, 09h44

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...

).
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 :

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

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à...
}

**jo_link_noir** · 25/04/2015, 13h50

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

**blackbird1** · 25/04/2015, 18h06

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

Code :

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

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

J'ai corrigé le init :

Code :

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

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 :

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
 
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 :

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

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 :

$ 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 !