C++ Program to Create Expression Tree from Prefix Expression

«
»
This C++ program, using recursion, evaluates a Prefix Expression in an Expression Tree. A binary expression tree is a specific application of a binary tree to evaluate certain expressions.

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

  1. /*
  2.  * C++ Program to Construct an Expression Tree for a Given Prefix Expression
  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.         void push(TreeNode *ptr)
  59.         {
  60.             if (top == NULL)
  61.                 top = new StackNode(ptr);
  62.             else
  63.             {
  64.                 StackNode *nptr = new StackNode(ptr);
  65.                 nptr->next = top;
  66.                 top = nptr;
  67.             }
  68.         }
  69.  
  70.         /** function to pop a node **/
  71.         TreeNode *pop()
  72.         {
  73.             if (top == NULL)
  74.             {
  75.                 cout<<"Underflow"<<endl;
  76.             }
  77.             else
  78.             {
  79.                 TreeNode *ptr = top->treeNode;
  80.                 top = top->next;
  81.                 return ptr;
  82.             }
  83.         }
  84.  
  85.         /** function to get top node **/
  86.         TreeNode *peek()
  87.         {
  88.             return top->treeNode;
  89.         }
  90.  
  91.  
  92.         /** function to insert character **/
  93.         void insert(char val)
  94.         {
  95.             if (isDigit(val))
  96.             {
  97.                 TreeNode *nptr = new TreeNode(val);
  98.                 push(nptr);
  99.             }
  100.             else if (isOperator(val))
  101.             {
  102.                 TreeNode *nptr = new TreeNode(val);
  103.                 nptr->left = pop();
  104.                 nptr->right = pop();
  105.                 push(nptr);
  106.             }
  107.             else
  108.             {
  109.                 cout<<"Invalid Expression"<<endl;
  110.                 return;
  111.             }
  112.         }
  113.  
  114.         /** function to check if digit **/
  115.         bool isDigit(char ch)
  116.         {
  117.             return ch >= '0' && ch <= '9';
  118.         }
  119.  
  120.         /** function to check if operator **/
  121.         bool isOperator(char ch)
  122.         {
  123.             return ch == '+' || ch == '-' || ch == '*' || ch == '/';
  124.         }
  125.  
  126.  
  127.         /** function to convert character to digit **/
  128.         int toDigit(char ch)
  129.         {
  130.             return ch - '0';
  131.         }
  132.  
  133.         /** function to build tree from input */
  134.  
  135.         void buildTree(string eqn)
  136.         {
  137.             for (int i = eqn.length() - 1; i >= 0; i--)
  138.                 insert(eqn[i]);
  139.         }
  140.  
  141.         /** function to evaluate tree */
  142.         double evaluate()
  143.         {
  144.             return evaluate(peek());
  145.         }
  146.  
  147.         /** function to evaluate tree */
  148.         double evaluate(TreeNode *ptr)
  149.         {
  150.             if (ptr->left == NULL && ptr->right == NULL)
  151.                 return toDigit(ptr->data);
  152.             else
  153.             {
  154.                 double result = 0.0;
  155.                 double left = evaluate(ptr->left);
  156.                 double right = evaluate(ptr->right);
  157.                 char op = ptr->data;
  158.                 switch (op)
  159.                 {
  160.                 case '+': 
  161.                     result = left + right; 
  162.                     break;
  163.                 case '-': 
  164.                     result = left - right; 
  165.                     break;
  166.                 case '*': 
  167.                     result = left * right; 
  168.                     break;
  169.                 case '/': 
  170.                     result = left / right; 
  171.                     break;
  172.                 default: 
  173.                     result = left + right; 
  174.                     break;
  175.                 }
  176.                 return result;
  177.             }
  178.         }
  179.  
  180.         /** function to get postfix expression */
  181.         void postfix()
  182.         {
  183.             postOrder(peek());
  184.         }
  185.  
  186.         /** post order traversal */
  187.         void postOrder(TreeNode *ptr)
  188.         {
  189.             if (ptr != NULL)
  190.             {
  191.                 postOrder(ptr->left);            
  192.                 postOrder(ptr->right);
  193.                 cout<<ptr->data;            
  194.             }    
  195.         }
  196.  
  197.         /** function to get infix expression */
  198.         void infix()
  199.         {
  200.             inOrder(peek());
  201.         }
  202.  
  203.         /** in order traversal */
  204.         void inOrder(TreeNode *ptr)
  205.         {
  206.             if (ptr != NULL)
  207.             {
  208.                 inOrder(ptr->left);
  209.                 cout<<ptr->data;   
  210.                 inOrder(ptr->right);            
  211.             }    
  212.         }
  213.  
  214.         /** function to get prefix expression */
  215.         void prefix()
  216.         {
  217.             preOrder(peek());
  218.         }
  219.  
  220.         /** pre order traversal */
  221.         void preOrder(TreeNode *ptr)
  222.         {
  223.             if (ptr != NULL)
  224.             {
  225.                 cout<<ptr->data;
  226.                 preOrder(ptr->left);
  227.                 preOrder(ptr->right);            
  228.             }    
  229.         }
  230. };
  231.  
  232.  
  233.  
  234. /** Main Contains menu **/
  235. int main()
  236. {
  237.     string s;
  238.     cout<<"Expression Tree Test"<<endl;
  239.     ExpressionTree et;
  240.     cout<<"\nEnter equation in Prefix form: ";
  241.     cin>>s;
  242.     et.buildTree(s);
  243.     cout<<"\nPrefix  : ";
  244.     et.prefix();
  245.     cout<<"\n\nInfix   : ";
  246.     et.infix();
  247.     cout<<"\n\nPostfix : ";
  248.     et.postfix();
  249.     cout<<"\n\nEvaluated Result : "<<et.evaluate();
  250.     return 0;
  251. }

$ g++ prefix.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

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

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

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 & technical discussions at Telegram SanfoundryClasses.