C++ Program to Implement Expression Tree Algorithm

«
»
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.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn