A Parse Tree in computer science is a binary tree structure and is used to visualize context-free grammar of words.
In this example the parse tree is used for a simple calculator with the basic arithmetic operations (+,-,*,/,^) and the simple round brackets ().
1 | /*
|
2 |     All class member functions are sorted by alphabetic order
|
3 |     between the constructor and destructor
|
4 | */
|
5 |
|
6 | //constructor
|
7 | Parsetree::Parsetree() {
|
8 |     list = new List<std::string>
|
9 |     root = NULL;
|
10 |     no_operator = 100;
|
11 | }
|
12 |
|
13 | struct Node<std::string> *Parsetree::append(std::string node) {
|
14 |     struct Node<std::string> *new_node = new struct Node<std::string>
|
15 |     new_node->node = node;
|
16 |     new_node->left = NULL;
|
17 |     new_node->right = NULL;
|
18 |     return new_node;
|
19 | }
|
20 |
|
21 | void Parsetree::append(struct Node<std::string> **head, std::string node) {
|
22 |     struct Node<std::string> *curr = *head;
|
23 |     if(curr == NULL) {
|
24 |         (*head) = append(node);
|
25 |         return;
|
26 |     }
|
27 |     if((priority(curr->node) >= priority(node)) && priority(node) < 100) {
|
28 |         struct Node<std::string> *temp = curr;
|
29 |         (*head) = append(node);
|
30 |         (*head)->left = temp;
|
31 |     }
|
32 |     if((priority(curr->node) < priority(node)) && priority(node) < 100) {
|
33 |         append(&curr->right, node);
|
34 |     }
|
35 |     if(priority(node) == 100) {
|
36 |         if(curr->left == NULL) append(&curr->left, node);
|
37 |         else append(&curr->right, node);
|
38 |     }
|
39 | }
|
40 |
|
41 | //funktion to calculate left and right leaf
|
42 | std::string Parsetree::calculate(std::string node1, std::string opera, std::string node2) {
|
43 |     double operand1 = fromString<double>(node1);
|
44 |     double operand2 = fromString<double>(node2);
|
45 |     double result;
|
46 |     
|
47 |     switch(opera[0]) {
|
48 |         case '+':
|
49 |             result = operand1 + operand2;
|
50 |         break;
|
51 |         case '-':
|
52 |             result = operand1 - operand2;
|
53 |         break;
|
54 |         case '*':
|
55 |             result = operand1 * operand2;
|
56 |         break;
|
57 |         case '/':
|
58 |             result = operand1 / operand2;
|
59 |         break;
|
60 |         case '^':
|
61 |             result = exp(log(fabs(operand1))*operand2);
|
62 |         break;
|
63 |     }
|
64 |     
|
65 |     return toString(result);;
|
66 | }
|
67 |
|
68 | //function to navigate through parsetree and destroy until root
|
69 | //by navigation it calculate both leafs and copy result to parent node
|
70 | void Parsetree::calculation(struct Node<std::string> **head) {
|
71 |     struct Node<std::string> *curr = *head;
|
72 |     if(priority(curr->node) == 100) return;
|
73 |     
|
74 |     calculation(&curr->left);
|
75 |     calculation(&curr->right);
|
76 |     
|
77 |     if(priority(curr->left->node) == 100 && priority(curr->right->node) == 100) {
|
78 |         (*head)->node = calculate((*head)->left->node, (*head)->node, (*head)->right->node);
|
79 |         struct Node<std::string> *temp_left = curr->left;
|
80 |         struct Node<std::string> *temp_right = curr->right;
|
81 |         
|
82 |         delete temp_left;
|
83 |         delete temp_right;
|
84 |         curr->left = NULL;
|
85 |         curr->right = NULL;
|
86 |         
|
87 |         return;
|
88 |     }
|
89 | }
|
90 |
|
91 | //just a public call function
|
92 | void Parsetree::calculation() {
|
93 |     if(root == NULL) return;
|
94 |     calculation(&root);
|
95 |     
|
96 |     std::cout << "Result: ";
|
97 |     print_tree(root);
|
98 | }
|
99 |
|
100 | //check brackets and when a multiplication operator is absent
|
101 | //then change source list
|
102 | bool Parsetree::check_brackets() {
|
103 |     struct Item<std::string> *curr = list->head();
|
104 |     if(curr && curr->next == NULL) return false;
|
105 |     struct Item<std::string> *prevx = NULL;
|
106 |     struct Item<std::string> *prevy = NULL;
|
107 |     int bracket = 0;
|
108 |     while(curr != NULL) {
|
109 |         if(curr && curr->item != "(") prevx = curr;
|
110 |         if(curr && curr->item != ")") prevy = curr;
|
111 |         if(curr && curr->item == "(") bracket++;
|
112 |         if(curr && curr->item == ")") bracket--;
|
113 |         if(prevx && priority(prevx->item) == 100 && curr->item == "(") list->insert_after(prevx, "*");
|
114 |         if(curr->item == ")" && curr->next->item == "(") list->insert_after(curr, "*");
|
115 |         curr = curr->next;
|
116 |     }
|
117 |     if(bracket != 0) return false;
|
118 |     return true;
|
119 | }
|
120 |
|
121 | //converts numbers with comma to the americam style
|
122 | //to example 1,000 = 1000
|
123 | std::string Parsetree::converter(std::string s) {
|
124 |     char *curr = new char[s.length()];
|
125 |     int index = 0;
|
126 |     int pos = 0;
|
127 |     bool found = false;
|
128 |     
|
129 |     for(std::string::iterator i = s.begin(); i != s.end(); i++) {
|
130 |         curr[index] = *i;
|
131 |         if(curr[index] == ',') found = true;
|
132 |         if(found == false) pos++;
|
133 |         index++;
|
134 |     }
|
135 |     delete [] curr;
|
136 |     
|
137 |     double number;
|
138 |     if(found == true) {
|
139 |         s.insert(pos,".");
|
140 |         s.erase(pos+1,1);
|
141 |         
|
142 |         number = fromString<double>(s);
|
143 |         number = number * 1000;
|
144 |         
|
145 |         return toString(number);
|
146 |     }
|
147 |     
|
148 |     return s;
|
149 | }
|
150 |
|
151 | //create parsetree
|
152 | bool Parsetree::create() {
|
153 |     if(check_brackets() == false) return false;
|
154 |     else {
|
155 |         bool brackets = false;
|
156 |         struct Item<std::string> *prevx = NULL;
|
157 |         struct Item<std::string> *prevy = NULL;
|
158 |         struct Item<std::string> *curr = list->head();
|
159 |         struct Node<std::string> *tree_root = NULL;
|
160 |         while(curr != NULL) {
|
161 |             if(prevx == NULL && priority(curr->item) < 100) append(&tree_root, "0");
|
162 |             if(curr && curr->item != "(" && brackets == false) prevx = curr;
|
163 |             if(curr && curr->item != ")") prevy = curr;
|
164 |             if(curr->item == "(") brackets = true;
|
165 |             if(curr->item == ")") brackets = false;
|
166 |             
|
167 |             if(brackets == true) {
|
168 |                 curr = in_brackets(&tree_root,curr,curr);
|
169 |                 brackets = false;
|
170 |                 if(curr->next != NULL) curr = curr->next;
|
171 |                 else break;
|
172 |             }
|
173 |             if(brackets == false) {
|
174 |                 if(curr->item != "(" && curr->item != ")") {
|
175 |                     append(&tree_root,curr->item);
|
176 |                     curr = curr->next;
|
177 |                 }
|
178 |             }
|
179 |         }
|
180 |         root = tree_root;
|
181 |     }
|
182 |     return true;
|
183 | }
|
184 |
|
185 | //part of tree print:
|
186 | // (dump_line, dump_node, dump_spaces, format_label, height, width)
|
187 | void Parsetree::dump_line(std::ostream &out, const Node<std::string> *node, unsigned line){
|
188 |     if(!node) return;
|
189 |     if(line == 1) {
|
190 |         //output root
|
191 |         dump_spaces(out, width(node->left));
|
192 |         out << format_label(node);
|
193 |         dump_spaces(out, width(node->right));
|
194 |     }
|
195 |     else {
|
196 |         //the roots are one level down and the line number is changed of both subtrees
|
197 |         dump_line(out, node->left, line-1);
|
198 |         dump_spaces(out, format_label(node).length());
|
199 |         dump_line(out, node->right, line-1);
|
200 |     }
|
201 | }
|
202 |
|
203 | //part of tree print:
|
204 | // (dump_line, dump_node, dump_spaces, format_label, height, width)
|
205 | void Parsetree::dump_node(std::ostream &out, const Node<std::string> *node) {
|
206 |     for(unsigned line = 1, h = height(node); line <= h; ++line) {
|
207 |         dump_line(out, node, line);
|
208 |         out.put('\n');
|
209 |     }
|
210 |     out.flush();
|
211 | }
|
212 |
|
213 | //part of tree print:
|
214 | // (dump_line, dump_node, dump_spaces, format_label, height, width)
|
215 | void Parsetree::dump_spaces(std::ostream &out, unsigned count) {
|
216 |     for(unsigned i = 0; i < count; ++i) {
|
217 |         out.put(' ');
|
218 |     }
|
219 | }
|
220 |
|
221 | //erase parsetree
|
222 | void Parsetree::erase(struct Node<std::string> **head) {
|
223 |     struct Node<std::string> *curr = *head;
|
224 |     if(curr == NULL) {
|
225 |         (*head) = curr;
|
226 |         return;
|
227 |     }
|
228 |     erase(&curr->left);
|
229 |     erase(&curr->right);
|
230 |     struct Node<std::string> *temp = curr;
|
231 |     delete temp;
|
232 |     curr = NULL;
|
233 | }
|
234 |
|
235 | //part of tree print:
|
236 | // (dump_line, dump_node, dump_spaces, format_label, height, width)
|
237 | std::string Parsetree::format_label(const Node<std::string> *node) {
|
238 |     if(node) {
|
239 |         std::ostringstream out;
|
240 |         out << node->node;
|
241 |         return out.str();
|
242 |     }
|
243 |     else return "";
|
244 | }
|
245 |
|
246 | //conversion from string to double
|
247 | template<class T> T Parsetree::fromString(const std::string& s) {
|
248 |     std::istringstream stream (s);
|
249 |     T t;
|
250 |     stream >> t;
|
251 |     return t;
|
252 | }
|
253 |
|
254 | //part of tree print:
|
255 | // (dump_line, dump_node, dump_spaces, format_label, height, width)
|
256 | unsigned Parsetree::height(const Node<std::string> *node) {
|
257 |     if(!node) return 0;
|
258 |     unsigned left_height = 0, right_height = 0;
|
259 |     
|
260 |     if(node->left) left_height = height(node->left);
|
261 |     if(node->right) right_height = height(node->right);
|
262 |     
|
263 |     // Der höchste Unterbaum bestimmt die Gesamthöhe
|
264 |     return std::max(left_height, right_height) + 1;
|
265 | }
|
266 |
|
267 | //walktrough round brackets and create subtrees and append to parsetree
|
268 | struct Item<std::string> *Parsetree::in_brackets(struct Node<std::string> **tree_root, struct Item<std::string> *prev, struct Item<std::string> *curr) {
|
269 |     struct Node<std::string> *subtree = NULL;
|
270 |     struct Node<std::string> *tree = *tree_root;
|
271 |     
|
272 |     while(curr && curr->item != ")") {
|
273 |         prev = curr - 1;
|
274 |         if(curr->item != "(") append(&subtree, curr->item);
|
275 |         curr = curr->next;
|
276 |     }
|
277 |     
|
278 |     if(curr->next->next != NULL) {
|
279 |         if(curr->item == ")" && priority(curr->next->item) > 1) {
|
280 |             push_right(&subtree, curr->next->item);
|
281 |             curr = curr->next;
|
282 |             if(curr->next != NULL) {
|
283 |                 if(priority(curr->next->item) == 100 && curr->next->item != "(") {
|
284 |                     append(&subtree, curr->next->item);
|
285 |                     curr = curr->next;
|
286 |                 }
|
287 |                 if(curr->item == "(") {
|
288 |                     struct Node<std::string> *temp = NULL;
|
289 |                     while(curr && curr->item != ")") {
|
290 |         
|
291 |                         if(curr->item != "(") append(&temp, curr->item);
|
292 |                          curr = curr->next;
|
293 |                     }
|
294 |                     push_right(&temp, "*");
|
295 |                     temp->right = append("1");
|
296 |                     subtree->right = temp;
|
297 |                 }
|
298 |             }
|
299 |         }
|
300 |     }
|
301 |     
|
302 |     if((*tree_root) == NULL) (*tree_root) = subtree;
|
303 |     else {
|
304 |         struct Node<std::string> *goto_operator = *tree_root;
|
305 |         while(goto_operator->right != NULL) goto_operator = goto_operator->right;
|
306 |         goto_operator->right = subtree;
|
307 |     }
|
308 |     return curr;
|
309 | }
|
310 |
|
311 | //just call function
|
312 | void Parsetree::insert(std::string item) { list->insert(converter(item)); }
|
313 |
|
314 | //mirror leaf nodes but not anymore needed
|
315 | void Parsetree::mirror(struct Node<std::string> **head) {
|
316 |     struct Node<std::string> *curr = *head;
|
317 |     if(curr == NULL) return;
|
318 |     else {
|
319 |         mirror(&curr->left);
|
320 |         mirror(&curr->right);
|
321 |         struct Node<std::string> *temp = curr->left;
|
322 |         curr->left = curr->right;
|
323 |         curr->right = temp;
|
324 |     }
|
325 | }
|
326 |
|
327 | //part of tree print:
|
328 | // (dump_line, dump_node, dump_spaces, format_label, height, width)
|
329 | void Parsetree::print_tree(Node<std::string> *tree) { dump_node(std::cout, tree); }
|
330 |
|
331 | //priority of operators or rules which parent nodes are have a higher level
|
332 | int Parsetree::priority(std::string c) {
|
333 |     if(c.compare("+") == 0) return 0;
|
334 |     if(c.compare("-") == 0) return 1;
|
335 |     if(c.compare("*") == 0) return 2;
|
336 |     if(c.compare("/") == 0) return 3;
|
337 |     if(c.compare("^") == 0) return 4;
|
338 |     return no_operator;
|
339 | }
|
340 |
|
341 | //just a call function
|
342 | void Parsetree::print() { list->print(); }
|
343 |
|
344 | //just a call function
|
345 | void Parsetree::print_tree() { print_tree(root); }
|
346 |
|
347 | //push a node to head right and appending current tree on left leaf for appending new right subtree
|
348 | void Parsetree::push_right(struct Node<std::string> **head, std::string item) {
|
349 |     struct Node<std::string> *curr = *head;
|
350 |     struct Node<std::string> *temp = append(item);
|
351 |     temp->left = curr;
|
352 |     (*head) = temp;
|
353 | }
|
354 |
|
355 | //conversion of double to string
|
356 | template<class T> std::string Parsetree::toString(const T& t) {
|
357 |     std::ostringstream stream;
|
358 |     stream << t;
|
359 |     return stream.str();
|
360 | }
|
361 |
|
362 | //part of tree print:
|
363 | // (dump_line, dump_node, dump_spaces, format_label, height, width)
|
364 | unsigned Parsetree::width(const Node<std::string> *node) {
|
365 |     if(!node) return 0;
|
366 |     unsigned left_width = 0, right_width = 0;
|
367 |     
|
368 |     if(node->left) left_width = width(node->left);
|
369 |     if(node->right) right_width = width(node->right);
|
370 |     
|
371 |     return left_width + format_label(node).length() + right_width;
|
372 | }
|
373 |
|
374 | //destuctor
|
375 | Parsetree::~Parsetree() {
|
376 |     list->erase();
|
377 |     delete list;
|
378 |     root = NULL;
|
379 |     delete root;
|
380 | } |