//Creating Parse Trees is one of the first step in compiler design. //Enter an expression with proper brackets and the program will create a parse tree of the expression //e.g. ((a+b)*(c-d)) //This program doesn't know about precedence so there must be 2 operands with an operator between and enclosed by proper brackets //Run in C++11 or higher #include #include using namespace std; class Node { public: char val; Node* left; Node* right; Node* parent; Node() { left=nullptr; right=nullptr; parent=nullptr; } }; class Tree { public: Node* root; Node* cur; Tree() { root=new Node(); cur=root; } void create_Left() { cur->left=new Node(); } void move_Left() { Node* temp=cur; cur=cur->left; cur->parent=temp; } void create_Right() { cur->right=new Node(); } void move_Right() { Node* temp=cur; cur=cur->right; cur->parent=temp; } void setVal(char ch) { cur->val=ch; } void moveAbove() { cur=cur->parent; } void printInorder(Node* node) { if (node == nullptr) return; printInorder(node->left); cout<val<<" "; printInorder(node->right); } void printPreorder(Node* node) { if (node == nullptr) return; cout<val<<" "; printPreorder(node->left); printPreorder(node->right); } // ~Tree() // { // cur=root; // while(cur->left) // { // // } // } }; void parse(char s[50],Tree* t) { char x; for(int i=0;icreate_Left(); t->create_Right(); t->move_Left(); } else if((int(x)>=65&&int(x)<=90)||(int(x)>=97&&int(x)<=122)) { t->setVal(x); t->moveAbove(); } else if(x=='+'||x=='-'||x=='*'||x=='/'||x=='%') { t->setVal(x); t->move_Right(); } if(x==')') { t->moveAbove(); } } } int main() { char s[50]; cout<<"Enter a string:"; cin>>s; Tree* t=new Tree(); parse(s,t); cout<<"Parse Tree Constructed!"<printInorder(t->root); cout<<"\nPreorder tree traversal is: "; t->printPreorder(t->root); return 0; }