C++ program to create expression tree

C++ program to create expression tree using postfix, prefix and infix expression.

C++ program to create expression tree using postfix expression

#include<iostream>
using namespace std;
struct tree_node
{
    char var;
    tree_node *left,*right;
} ;
class exp_tree
{
    char post[30];
    tree_node *root;
public:
    exp_tree()
    {
        root=NULL;
    }
    void get_exp()
    {
        cout<<"Enter the postfix expression ";
        cin>>post;
    }
    tree_node* get_root()
    {
        return root;
    }
    void exp_to_tree();
    void inorder(tree_node *);
    void preorder(tree_node *);
    void postorder(tree_node *);
};
void exp_tree::exp_to_tree()
{
    int top=-1,z;
    tree_node *stack[20];
    for(int i=0;post[i]!=0;i++)
    {
        stack[++top]=new tree_node;
        if(post[i]>=97&&post[i]<=122)
        {
            stack[top]->var=post[i];
            stack[top]->left=stack[top]->right=NULL;
        }
        else
        {
            stack[top]->var=post[i];
            stack[top]->left=stack[top-2];
            stack[top]->right=stack[top-1];
            top=top-2;
            root=stack[top]=stack[top+2];
        }
    }
}
void exp_tree::inorder(tree_node *temp)
{
    if(temp==NULL)
        return;
    inorder(temp->left);
    cout<<temp->var;
    inorder(temp->right);
}
void exp_tree::postorder(tree_node *temp)
{
    if(temp==NULL)
        return;
    postorder(temp->left);
    postorder(temp->right);
    cout<<temp->var;
}
void exp_tree::preorder(tree_node *temp)
{
    if(temp==NULL)
        return;
    cout<<temp->var;
    preorder(temp->left);
    preorder(temp->right);
}
int main()
{
    exp_tree exp;
    exp.get_exp();
    exp.exp_to_tree();
    cout<<"Expression tree Successfully created "<<endl;
    cout<<"Inorder Traversal : ";
    exp.inorder(exp.get_root());
    cout<<endl<<"Postorder Traversal : ";
    exp.postorder(exp.get_root());
    cout<<endl<<"Preorder Traversal : ";
    exp.preorder(exp.get_root());
    return 0;
}

OUTPUT

C++ program to create expression tree using prefix expression

#include<iostream>
#include<string.h>
using namespace std;
struct tree_node
{
    char var;
    tree_node *left,*right;
} ;
class exp_tree
{
    char pre[30];
    tree_node *root;
public:
    exp_tree()
    {
        root=NULL;
    }
    void get_exp()
    {
        cout<<"Enter the prefix expression ";
        cin>>pre;
    }
    tree_node* get_root()
    {
        return root;
    }
    void exp_to_tree();
    void inorder(tree_node *);
    void preorder(tree_node *);
    void postorder(tree_node *);
};
void exp_tree::exp_to_tree()
{
    int top=-1,z;
    tree_node *stack[20];
    strrev(pre);
    for(int i=0;pre[i]!=0;i++)
    {
        stack[++top]=new tree_node;
        if(pre[i]>=97&&pre[i]<=122)
        {
            stack[top]->var=pre[i];
            stack[top]->left=stack[top]->right=NULL;
        }
        else
        {
            stack[top]->var=pre[i];
            stack[top]->left=stack[top-1];
            stack[top]->right=stack[top-2];
            top=top-2;
            root=stack[top]=stack[top+2];
        }
    }
}
void exp_tree::inorder(tree_node *temp)
{
    if(temp==NULL)
        return;
    inorder(temp->left);
    cout<<temp->var;
    inorder(temp->right);
}
void exp_tree::postorder(tree_node *temp)
{
    if(temp==NULL)
        return;
    postorder(temp->left);
    postorder(temp->right);
    cout<<temp->var;
}
void exp_tree::preorder(tree_node *temp)
{
    if(temp==NULL)
        return;
    cout<<temp->var;
    preorder(temp->left);
    preorder(temp->right);
}
int main()
{
    exp_tree exp;
    exp.get_exp();
    exp.exp_to_tree();
    cout<<"Expression tree Successfully created "<<endl;
    cout<<"Inorder Traversal   : ";
    exp.inorder(exp.get_root());
    cout<<endl<<"Postorder Traversal : ";
    exp.postorder(exp.get_root());
    cout<<endl<<"Preorder Traversal  : ";
    exp.preorder(exp.get_root());
    return 0;
}

OUTPUT

C++ program to create expression tree using infix expression

#include<iostream>
using namespace std;
struct tree_node
{
    char var;
    tree_node *left,*right;
} ;
class exp_tree
{
    char post[30],inf[30];
    tree_node *root;
public:
    exp_tree()
    {
        root=NULL;
    }
    void get_exp()
    {
        cout<<"Enter the infix expression ";
        cin>>inf;
    }
    tree_node* get_root()
    {
        return root;
    }
    void convert();
    void exp_to_tree();
    void inorder(tree_node *);
    void preorder(tree_node *);
    void postorder(tree_node *);
};
void exp_tree::convert()
{
    int y=0,top=-1,stac[10];
    for(int i=0;inf[i]!=0;i++)
    {
        if(inf[i]>=97&&inf[i]<=122)
            post[y++]=inf[i];
        else
        {
            switch(inf[i])
            {
            case '+':
            case '-':
                while(top>=0&&stac[top]!='(')
                    post[y++]=stac[top--];
                stac[++top]=inf[i];
                break;
                case '*':
                case '/':
                    while(stac[top]!='+'&&stac[top]!='-'&&top>=0&&stac[top]!='(')
                         post[y++]=stac[top--];
                    stac[++top]=inf[i];
                    break;
                case '^':
                    stac[++top]=inf[i];
                    break;
                case '(':
                    stac[++top]=inf[i];
                    break;
                case ')':
                    while(stac[top]!='(')
                        post[y++]=stac[top--];
                    top--;
                    break;
                }
        }
    }
    while(top>=0)
        post[y++]=stac[top--];
    post[y]=0;
}
void exp_tree::exp_to_tree()
{
    int top=-1,z;
    tree_node *stack[20];
    for(int i=0;post[i]!=0;i++)
    {
        stack[++top]=new tree_node;
        if(post[i]>=97&&post[i]<=122)
        {
            stack[top]->var=post[i];
            stack[top]->left=stack[top]->right=NULL;
        }
        else
        {
            stack[top]->var=post[i];
            stack[top]->left=stack[top-2];
            stack[top]->right=stack[top-1];
            top=top-2;
            root=stack[top]=stack[top+2];
        }
    }
}
void exp_tree::inorder(tree_node *temp)
{
    if(temp==NULL)
        return;
    inorder(temp->left);
    cout<<temp->var;
    inorder(temp->right);
}
void exp_tree::postorder(tree_node *temp)
{
    if(temp==NULL)
        return;
    postorder(temp->left);
    postorder(temp->right);
    cout<<temp->var;
}
void exp_tree::preorder(tree_node *temp)
{
    if(temp==NULL)
        return;
    cout<<temp->var;
    preorder(temp->left);
    preorder(temp->right);
}
int main()
{
    exp_tree exp;
    exp.get_exp();
    exp.convert();
    exp.exp_to_tree();
    cout<<"Expression tree Successfully created "<<endl;
    cout<<"Inorder Traversal : ";
    exp.inorder(exp.get_root());
    cout<<endl<<"Postorder Traversal : ";
    exp.postorder(exp.get_root());
    cout<<endl<<"Preorder Traversal : ";
    exp.preorder(exp.get_root());
    return 0;
}

OUTPUT