Expression Tree in C++

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.

```
/*
```

 * C++ Program to Implement Expression Tree

```
 */
```
```
#include <iostream>
```
```
#include <cstdlib>
```
```
#include <cstdio>     
```
```
#include <cstring> 
```
```
using namespace std;
```
```
 
```
```
/** class TreeNode **/
```
```
class TreeNode
```
```
{       
```
```
    public:
```
```
        char data;
```
```
        TreeNode *left, *right;
```
```
        /** constructor **/
```
```
        TreeNode(char data)
```
```
        {
```
```
            this->data = data;
```
```
            this->left = NULL;
```
```
            this->right = NULL;
```
```
        }
```
```
}; 
```
```
 
```
```
/** class StackNode **/
```
```
class StackNode
```
```
{    
```
```
    public:
```
```
        TreeNode *treeNode;
```
```
        StackNode *next;
```
```
        /** constructor **/ 
```
```
        StackNode(TreeNode *treeNode)
```
```
        {
```
```
            this->treeNode = treeNode;
```
```
            next = NULL;
```
```
        }
```
```
};
```
```
 
```
```
 
```
```
class ExpressionTree
```
```
{
```
```
    private:
```
```
        StackNode *top;
```
```
    public:
```
```
        /** constructor **/ 
```
```
        ExpressionTree()
```
```
        {
```
```
            top = NULL;
```
```
        }
```
```
 
```
```
        /** function to clear tree **/
```
```
        void clear()
```
```
        {
```
```
            top = NULL;
```
```
        }
```
```
 
```
```
        /** function to push a node **/
```
```
 
```
```
        void push(TreeNode *ptr)
```
```
        {
```
```
            if (top == NULL)
```

                top = new StackNode(ptr);

```
            else
```
```
            {
```

                StackNode *nptr = new StackNode(ptr);

```
                nptr->next = top;
```
```
                top = nptr;
```
```
            }
```
```
        }
```
```
 
```
```
        /** function to pop a node **/
```
```
        TreeNode *pop()
```
```
        {
```
```
            if (top == NULL)
```
```
            {
```

                cout<<"Underflow"<<endl;

```
            }
```
```
            else
```
```
            {
```

                TreeNode *ptr = top->treeNode;

```
                top = top->next;
```
```
                return ptr;
```
```
            }
```
```
        }
```
```
 
```

        /** function to get top node **/

```
        TreeNode *peek()
```
```
        {
```
```
            return top->treeNode;
```
```
        }
```
```
 
```
```
 
```

        /** function to insert character **/

```
        void insert(char val)
```
```
        {
```
```
            if (isDigit(val))
```
```
            {
```

                TreeNode *nptr = new TreeNode(val);

```
                push(nptr);
```
```
            }
```
```
            else if (isOperator(val))
```
```
            {
```

                TreeNode *nptr = new TreeNode(val);

```
                nptr->left = pop();
```
```
                nptr->right = pop();
```
```
                push(nptr);
```
```
            }
```
```
            else
```
```
            {
```

                cout<<"Invalid Expression"<<endl;

```
                return;
```
```
            }
```
```
        }
```
```
 
```

        /** function to check if digit **/

```
        bool isDigit(char ch)
```
```
        {
```

            return ch >= '0' && ch <= '9';

```
        }
```
```
 
```

        /** function to check if operator **/

```
        bool isOperator(char ch)
```
```
        {
```

            return ch == '+' || ch == '-' || ch == '*' || ch == '/';

```
        }
```
```
 
```
```
 
```

        /** function to convert character to digit **/

```
        int toDigit(char ch)
```
```
        {
```
```
            return ch - '0';
```
```
        }
```
```
 
```

        /** function to build tree from input */

```
 
```
```
        void buildTree(string eqn)
```
```
        {
```

            for (int i = eqn.length() - 1; i >= 0; i--)

```
                insert(eqn[i]);
```
```
        }
```
```
 
```

        /** function to evaluate tree */

```
        double evaluate()
```
```
        {
```
```
            return evaluate(peek());
```
```
        }
```
```
 
```

        /** function to evaluate tree */

```
        double evaluate(TreeNode *ptr)
```
```
        {
```

            if (ptr->left == NULL && ptr->right == NULL)

                return toDigit(ptr->data);

```
            else
```
```
            {
```
```
                double result = 0.0;
```

                double left = evaluate(ptr->left);

                double right = evaluate(ptr->right);

```
                char op = ptr->data;
```
```
                switch (op)
```
```
                {
```
```
                case '+': 
```

                    result = left + right;

```
                    break;
```
```
                case '-': 
```

                    result = left - right;

```
                    break;
```
```
                case '*': 
```

                    result = left * right;

```
                    break;
```
```
                case '/': 
```

                    result = left / right;

```
                    break;
```
```
                default: 
```

                    result = left + right;

```
                    break;
```
```
                }
```
```
                return result;
```
```
            }
```
```
        }
```
```
 
```

        /** function to get postfix expression */

```
        void postfix()
```
```
        {
```
```
            postOrder(peek());
```
```
        }
```
```
 
```
```
        /** post order traversal */
```
```
        void postOrder(TreeNode *ptr)
```
```
        {
```
```
            if (ptr != NULL)
```
```
            {
```

                postOrder(ptr->left);

```
                postOrder(ptr->right);
```

                cout<<ptr->data;

```
            }    
```
```
        }
```
```
 
```

        /** function to get infix expression */

```
        void infix()
```
```
        {
```
```
            inOrder(peek());
```
```
        }
```
```
 
```
```
        /** in order traversal */
```
```
        void inOrder(TreeNode *ptr)
```
```
        {
```
```
            if (ptr != NULL)
```
```
            {
```
```
                inOrder(ptr->left);
```
```
                cout<<ptr->data;   
```

                inOrder(ptr->right);

```
            }    
```
```
        }
```
```
 
```

        /** function to get prefix expression */

```
        void prefix()
```
```
        {
```
```
            preOrder(peek());
```
```
        }
```
```
 
```
```
        /** pre order traversal */
```
```
        void preOrder(TreeNode *ptr)
```
```
        {
```
```
            if (ptr != NULL)
```
```
            {
```
```
                cout<<ptr->data;
```
```
                preOrder(ptr->left);
```

                preOrder(ptr->right);

```
            }    
```
```
        }
```
```
};
```
```
 
```
```
 
```
```
 
```
```
/** Main Contains menu **/
```
```
int main()
```
```
{
```
```
    string s;
```
```
    cout<<"Expression Tree Test"<<endl;
```
```
    ExpressionTree et;
```

    cout<<"\nEnter equation in prefix form: ";

```
    cin>>s;
```
```
    et.buildTree(s);
```
```
    cout<<"\nPrefix  : ";
```
```
    et.prefix();
```
```
    cout<<"\n\nInfix   : ";
```
```
    et.infix();
```
```
    cout<<"\n\nPostfix : ";
```
```
    et.postfix();
```

    cout<<"\n\nEvaluated Result : "<<et.evaluate();

```
    return 0;
```
```
}
```

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

$ 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

Check this: Computer Science MCQs | Programming Books

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.

```
/*
```

* C++ Program to Implement Expression Tree Algorithm

```
*/
```
```
#include <iostream>
```
```
#include <conio.h>
```
```
using namespace std;
```
```
struct tree
```
```
{
```
```
    char data;
```
```
    tree *l, *r;
```

}*root = NULL, *p = NULL, *t = NULL, *y = NULL;

```
struct node
```
```
{
```
```
       tree *pt;
```
```
       node *next;
```
```
}*top = NULL, *q = NULL, *np = NULL;
```
```
void push(tree *ptr)
```
```
{
```
```
    np = new node;
```
```
    np->pt = ptr;
```
```
    np->next = NULL;
```
```
    if (top == NULL)
```
```
    {
```
```
        top = np;
```
```
    }
```
```
    else
```
```
    {
```
```
        q = top;
```
```
        top = np;
```
```
        np->next = q;
```
```
    }
```
```
}
```
```
tree *pop()
```
```
{
```
```
    if (top == NULL)
```
```
    {
```
```
        cout<<"underflow\n";
```
```
    }
```
```
    else
```
```
    {
```
```
        q = top;
```
```
        top = top->next;
```
```
        return(q->pt);
```
```
        delete(q);
```
```
    }
```
```
}
```
```
void oprnd_str(char val)
```
```
{
```
```
    if (val >= 48 && val <= 57)
```
```
    {
```
```
        t = new tree;
```
```
        t->data = val;
```
```
        t->l = NULL;
```
```
        t->r = NULL;
```
```
        push(t);
```
```
    }
```
```
    else if (val >= 42 && val <= 47)
```
```
    {
```
```
        p = new tree;
```
```
        p->data = val;
```
```
        p->l = pop();
```
```
        p->r = pop();
```
```
        push(p);
```
```
    }
```
```
}
```
```
char pstorder(tree *w)
```
```
{
```
```
    if (w != NULL)
```
```
    {
```
```
        pstorder(w->l);
```
```
        pstorder(w->r);
```
```
        cout<<w->data;
```
```
    }
```
```
}
```
```
int main()
```
```
{
```
```
    char a[15];
```
```
    int i;
```
```
    int j = -1;
```

    cout<<"enter the value of character string\n";

```
    cin>>a;
```
```
    i = strlen(a);
```
```
    while (i >= 0)
```
```
    {
```
```
        i--;
```
```
        oprnd_str(a[i]);
```
```
    }
```
```
    cout<<"displaying in postorder\n";
```
```
    pstorder(pop());
```
```
    getch();
```
```
}
```

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

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

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

« Prev - C++ Program to Implement Cartesian Tree

» Next - C++ Program to Implement Fusion Tree

Next Steps:

Get Free Certificate of Merit in Data Structure I
Participate in Data Structure I Certification Contest
Become a Top Ranker in Data Structure I
Take Data Structure I Tests
Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Related Posts:

Buy Programming Books
Buy Computer Science Books
Apply for Information Technology Internship
Practice Programming MCQs
Practice Design & Analysis of Algorithms MCQ

Recommended Articles: