Parse Tree

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

item.h
1#ifndef item_h
2#define item_h
3
4template<class T>
5struct Item {
6  T item;
7  struct Item *next;
8};
9
10#endif
list.h
1#ifndef list_h
2#define list_h
3#include "item.h"
4
5template<class T>
6class List {
7private:
8  Item<T> *list;
9  
10  struct Item<T> *append(T);
11  void append(struct Item<T> **, T);
12  void erase(struct Item<T> **, T);
13  void erase(struct Item<T> **, struct Item<T> *);
14  void erase(struct Item<T> **);
15  std::string get_list_as_string(struct Item<T> **);
16  void print(struct Item<T> **);
17  void push(struct Item<T> **, T);
18  void reverse(struct Item<T> **);
19  struct Item<T> *search(struct Item<T> **, T);
20  void swap(struct Item<T> **, T, T);
21  
22public:
23  List();
24  void erase(struct Item<T> *);
25  void erase(T);
26  void erase();
27  std::string get_list_as_string();
28  struct Item<T> *head();
29  void insert(T);
30  void insert_after(struct Item<T> *, T);
31  void print();
32  void push(T);
33  void reverse();
34  void swap(T, T);
35  ~List();
36};
37
38//appending class member functions
39#include "list.m"
40#endif
node.h
1#ifndef node_h
2#define node_h
3
4template<class T>
5struct Node {
6    T node;
7    struct Node *left;
8    struct Node *right;
9};
10
11#endif
parsetree.h
1#ifndef parsetree_h
2#define parsetree_h
3#include <sstream>
4#include <string>
5#include <stdlib.h>
6#include <cmath>
7#include "node.h"
8
9class Parsetree {
10private:
11    Node<std::string> *root;
12    List<std::string> *list;
13    int no_operator;
14  
15    struct Node<std::string> *append(std::string);
16    void append(struct Node<std::string> **, std::string);
17    void push_right(struct Node<std::string> **, std::string);
18    void mirror(struct Node<std::string> **);
19    void erase(struct Node<std::string> **);
20    unsigned height(const Node<std::string> *);
21    unsigned width(const Node<std::string> *);
22    std::string format_label(const Node<std::string> *);
23    void dump_spaces(std::ostream &, unsigned);
24    void dump_line(std::ostream &, const Node<std::string> *, unsigned);
25    void dump_node(std::ostream &, const Node<std::string> *);
26    int priority(std::string);
27    bool check_brackets();
28    struct Item<std::string> *in_brackets(struct Node<std::string> **, struct Item<std::string> *, struct Item<std::string> *);
29    std::string converter(std::string);
30    template<class T> std::string toString(const T &);
31    template<class T> T fromString(const std::string &);
32    std::string calculate(std::string, std::string, std::string);
33    void calculation(struct Node<std::string> **);
34    void print_tree(Node<std::string> *);
35public:
36    Parsetree();
37    void insert(std::string);
38    bool create();
39    void calculation();
40    void print();
41    void print_tree();
42    ~Parsetree();
43};
44
45//appending class member functions
46#include "parsetree.m"
47#endif
parsetree.m
1/*
2    All class member functions are sorted by alphabetic order
3    between the constructor and destructor
4*/
5
6//constructor
7Parsetree::Parsetree() {
8    list = new List<std::string>
9    root = NULL;
10    no_operator = 100;
11}
12
13struct 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
21void 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
42std::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
70void 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
92void 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
102bool 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
123std::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
152bool 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)
187void 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)
205void 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)
215void 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
222void 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)
237std::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
247template<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)
256unsigned 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
268struct 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
312void Parsetree::insert(std::string item) { list->insert(converter(item)); }
313
314//mirror leaf nodes but not anymore needed
315void 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)
329void 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
332int 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
342void Parsetree::print() { list->print(); }
343
344//just a call function
345void 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
348void 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
356template<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)
364unsigned 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
375Parsetree::~Parsetree() {
376    list->erase();
377    delete list;
378    root = NULL;
379    delete root;
380}
main.cpp
1#include <iostream>
2#include "list.h"
3#include "parsetree.h"
4using namespace std;
5
6bool checkop(char o) {
7  if(o == '-') return true;
8  if(o == '+') return true;
9  if(o == '*') return true;
10  if(o == '/') return true;
11  if(o == '(') return true;
12  if(o == ')') return true;
13  if(o == '^') return true;
14  return false;
15}
16
17int main() {
18  Parsetree *list = new Parsetree;
19  char c;
20  string line;
21  
22  cout << "Input: ";
23  
24  getline(cin, line);
25  istringstream iss(line);
26  string s = "";
27  
28  while (iss >> c) {
29    if((c >= '0' && c <= '9') || (c == '.' | c == ',' )) {
30      s += c;
31      c = ' ';
32    }
33    if(checkop(c) == true) {
34      if(s.compare("") != 0) {
35        list->insert(s);
36      }
37     
38      s = c;
39      list->insert(s);
40      s = "";
41     
42    }
43  }
44  
45  list->insert(s);
46  if(list->create()) {
47      list->print();
48    
49      cout << endl << "Parsetree:" << endl;
50      list->print_tree();
51      list->calculation();
52  }
53  
54  delete list;
55  
56  return 0;
57}