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 :
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 :
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 #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); };
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; }
Partager