C++ Program to Implement Expression Tree

The expression tree is a binary tree. It contains the operand at the leaf nodes and the rest of the nodes are filled with the operator. The operands and operators can be sorted in any order (ascending, descending). It is also used to evaluate postfix, prefix, and infix expressions.

Method 1: Implementation of the Expression Tree

This C++ Program demonstrates the implementation of the Expression Tree.

Here is source code of the C++ Program to demonstrate the implementation of Expression Tree. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C++ Program to Implement Expression Tree
  3.  */
  4. #include <iostream>
  5. #include <cstdlib>
  6. #include <cstdio>     
  7. #include <cstring> 
  8. using namespace std;
  9.  
  10. /** class TreeNode **/
  11. class TreeNode
  12. {       
  13.     public:
  14.         char data;
  15.         TreeNode *left, *right;
  16.         /** constructor **/
  17.         TreeNode(char data)
  18.         {
  19.             this->data = data;
  20.             this->left = NULL;
  21.             this->right = NULL;
  22.         }
  23. }; 
  24.  
  25. /** class StackNode **/
  26. class StackNode
  27. {    
  28.     public:
  29.         TreeNode *treeNode;
  30.         StackNode *next;
  31.         /** constructor **/ 
  32.         StackNode(TreeNode *treeNode)
  33.         {
  34.             this->treeNode = treeNode;
  35.             next = NULL;
  36.         }
  37. };
  38.  
  39.  
  40. class ExpressionTree
  41. {
  42.     private:
  43.         StackNode *top;
  44.     public:
  45.         /** constructor **/ 
  46.         ExpressionTree()
  47.         {
  48.             top = NULL;
  49.         }
  50.  
  51.         /** function to clear tree **/
  52.         void clear()
  53.         {
  54.             top = NULL;
  55.         }
  56.  
  57.         /** function to push a node **/
  58.  
  59.         void push(TreeNode *ptr)
  60.         {
  61.             if (top == NULL)
  62.                 top = new StackNode(ptr);
  63.             else
  64.             {
  65.                 StackNode *nptr = new StackNode(ptr);
  66.                 nptr->next = top;
  67.                 top = nptr;
  68.             }
  69.         }
  70.  
  71.         /** function to pop a node **/
  72.         TreeNode *pop()
  73.         {
  74.             if (top == NULL)
  75.             {
  76.                 cout<<"Underflow"<<endl;
  77.             }
  78.             else
  79.             {
  80.                 TreeNode *ptr = top->treeNode;
  81.                 top = top->next;
  82.                 return ptr;
  83.             }
  84.         }
  85.  
  86.         /** function to get top node **/
  87.         TreeNode *peek()
  88.         {
  89.             return top->treeNode;
  90.         }
  91.  
  92.  
  93.         /** function to insert character **/
  94.         void insert(char val)
  95.         {
  96.             if (isDigit(val))
  97.             {
  98.                 TreeNode *nptr = new TreeNode(val);
  99.                 push(nptr);
  100.             }
  101.             else if (isOperator(val))
  102.             {
  103.                 TreeNode *nptr = new TreeNode(val);
  104.                 nptr->left = pop();
  105.                 nptr->right = pop();
  106.                 push(nptr);
  107.             }
  108.             else
  109.             {
  110.                 cout<<"Invalid Expression"<<endl;
  111.                 return;
  112.             }
  113.         }
  114.  
  115.         /** function to check if digit **/
  116.         bool isDigit(char ch)
  117.         {
  118.             return ch >= '0' && ch <= '9';
  119.         }
  120.  
  121.         /** function to check if operator **/
  122.         bool isOperator(char ch)
  123.         {
  124.             return ch == '+' || ch == '-' || ch == '*' || ch == '/';
  125.         }
  126.  
  127.  
  128.         /** function to convert character to digit **/
  129.         int toDigit(char ch)
  130.         {
  131.             return ch - '0';
  132.         }
  133.  
  134.         /** function to build tree from input */
  135.  
  136.         void buildTree(string eqn)
  137.         {
  138.             for (int i = eqn.length() - 1; i >= 0; i--)
  139.                 insert(eqn[i]);
  140.         }
  141.  
  142.         /** function to evaluate tree */
  143.         double evaluate()
  144.         {
  145.             return evaluate(peek());
  146.         }
  147.  
  148.         /** function to evaluate tree */
  149.         double evaluate(TreeNode *ptr)
  150.         {
  151.             if (ptr->left == NULL && ptr->right == NULL)
  152.                 return toDigit(ptr->data);
  153.             else
  154.             {
  155.                 double result = 0.0;
  156.                 double left = evaluate(ptr->left);
  157.                 double right = evaluate(ptr->right);
  158.                 char op = ptr->data;
  159.                 switch (op)
  160.                 {
  161.                 case '+': 
  162.                     result = left + right; 
  163.                     break;
  164.                 case '-': 
  165.                     result = left - right; 
  166.                     break;
  167.                 case '*': 
  168.                     result = left * right; 
  169.                     break;
  170.                 case '/': 
  171.                     result = left / right; 
  172.                     break;
  173.                 default: 
  174.                     result = left + right; 
  175.                     break;
  176.                 }
  177.                 return result;
  178.             }
  179.         }
  180.  
  181.         /** function to get postfix expression */
  182.         void postfix()
  183.         {
  184.             postOrder(peek());
  185.         }
  186.  
  187.         /** post order traversal */
  188.         void postOrder(TreeNode *ptr)
  189.         {
  190.             if (ptr != NULL)
  191.             {
  192.                 postOrder(ptr->left);            
  193.                 postOrder(ptr->right);
  194.                 cout<<ptr->data;            
  195.             }    
  196.         }
  197.  
  198.         /** function to get infix expression */
  199.         void infix()
  200.         {
  201.             inOrder(peek());
  202.         }
  203.  
  204.         /** in order traversal */
  205.         void inOrder(TreeNode *ptr)
  206.         {
  207.             if (ptr != NULL)
  208.             {
  209.                 inOrder(ptr->left);
  210.                 cout<<ptr->data;   
  211.                 inOrder(ptr->right);            
  212.             }    
  213.         }
  214.  
  215.         /** function to get prefix expression */
  216.         void prefix()
  217.         {
  218.             preOrder(peek());
  219.         }
  220.  
  221.         /** pre order traversal */
  222.         void preOrder(TreeNode *ptr)
  223.         {
  224.             if (ptr != NULL)
  225.             {
  226.                 cout<<ptr->data;
  227.                 preOrder(ptr->left);
  228.                 preOrder(ptr->right);            
  229.             }    
  230.         }
  231. };
  232.  
  233.  
  234.  
  235. /** Main Contains menu **/
  236. int main()
  237. {
  238.     string s;
  239.     cout<<"Expression Tree Test"<<endl;
  240.     ExpressionTree et;
  241.     cout<<"\nEnter equation in prefix form: ";
  242.     cin>>s;
  243.     et.buildTree(s);
  244.     cout<<"\nPrefix  : ";
  245.     et.prefix();
  246.     cout<<"\n\nInfix   : ";
  247.     et.infix();
  248.     cout<<"\n\nPostfix : ";
  249.     et.postfix();
  250.     cout<<"\n\nEvaluated Result : "<<et.evaluate();
  251.     return 0;
  252. }

advertisement
advertisement
$ g++ expression_tree.cpp
$ a.out
 
Expression Tree Test
 
Enter equation in prefix form: +-+7*/935/82*/625
 
Prefix  : +-+7*/935/82*/625
 
Infix   : 7+9/3*5-8/2+6/2*5
 
Postfix : 793/5*+82/-62/5*+
 
Evaluated Result : 33
------------------
(program exited with code: 1)
Press return to continue

Method 2: Implement Expression Tree Algorithm

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
This C++ program implements the expression tree algorithm which consists of operands as terminal nodes and operators as root or sub root nodes.

Here is the source code of the C++ program which takes the prefix expression as an input and generates the corresponding expression tree traversed in postorder. This C++ program is successfully compiled and run on DevCpp, a C++ compiler. The program output is also shown below.

  1. /*
  2. * C++ Program to Implement Expression Tree Algorithm
  3. */
  4. #include <iostream>
  5. #include <conio.h>
  6. using namespace std;
  7. struct tree
  8. {
  9.     char data;
  10.     tree *l, *r;
  11. }*root = NULL, *p = NULL, *t = NULL, *y = NULL;
  12. struct node
  13. {
  14.        tree *pt;
  15.        node *next;
  16. }*top = NULL, *q = NULL, *np = NULL;
  17. void push(tree *ptr)
  18. {
  19.     np = new node;
  20.     np->pt = ptr;
  21.     np->next = NULL;
  22.     if (top == NULL)
  23.     {
  24.         top = np;
  25.     }
  26.     else
  27.     {
  28.         q = top;
  29.         top = np;
  30.         np->next = q;
  31.     }
  32. }
  33. tree *pop()
  34. {
  35.     if (top == NULL)
  36.     {
  37.         cout<<"underflow\n";
  38.     }
  39.     else
  40.     {
  41.         q = top;
  42.         top = top->next;
  43.         return(q->pt);
  44.         delete(q);
  45.     }
  46. }
  47. void oprnd_str(char val)
  48. {
  49.     if (val >= 48 && val <= 57)
  50.     {
  51.         t = new tree;
  52.         t->data = val;
  53.         t->l = NULL;
  54.         t->r = NULL;
  55.         push(t);
  56.     }
  57.     else if (val >= 42 && val <= 47)
  58.     {
  59.         p = new tree;
  60.         p->data = val;
  61.         p->l = pop();
  62.         p->r = pop();
  63.         push(p);
  64.     }
  65. }
  66. char pstorder(tree *w)
  67. {
  68.     if (w != NULL)
  69.     {
  70.         pstorder(w->l);
  71.         pstorder(w->r);
  72.         cout<<w->data;
  73.     }
  74. }
  75. int main()
  76. {
  77.     char a[15];
  78.     int i;
  79.     int j = -1;
  80.     cout<<"enter the value of character string\n";
  81.     cin>>a;
  82.     i = strlen(a);
  83.     while (i >= 0)
  84.     {
  85.         i--;
  86.         oprnd_str(a[i]);
  87.     }
  88.     cout<<"displaying in postorder\n";
  89.     pstorder(pop());
  90.     getch();
  91. }

advertisement
Output:
enter the value of character string
-+-5/763*48
displaying in postorder
576/-3+48*-

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.