Question

Write a C++ function that takes in an arithmetic expression in prefix notation and converts it into a binary tree, such that each operation is stored in a node whose left subtree stores the left operand, and whose right subtree stores the right operand.

Answer 1

• in this program we convert the input prefix notation into a binary tree
• the tree is implemented using a linked list of node structure it have both left and right link
• left operand in left child and right operand in right child
• after tree creation we check it by printing the infix notation and postfix notation from the tree we built from the prefix notation.

the code is given below

#include <iostream>

using namespace std;
//structure for node of a tree
typedef struct node{
    char data;
    struct node*left,*right;
}node;
//recursive functon for building tree
char* buildtree(node** x,char * y)
{
    if(* y=='\0')
    return '\0';
    while(1)
    {
        char* a='\0';
        if(*x==NULL)
        {
            node* newnode=(node*)malloc(sizeof(node));
            newnode->data=*y;
            newnode->left=NULL;
            newnode->right=NULL;
            *x=newnode;
        }
        else
        {
            if((*y>='a' && *y<='z')|| (*y>='0'&&*y<='9'))
            return y;
        
        a=buildtree(&(*x)->left,y+1);
        a=buildtree(&(*x)->right,a+1);
        return a;
    
        }   
    }
}
//function for infix notation
void infix(node *x)
{
    if (x==NULL)
    return ;
    else
    {
        infix(x->left);
        cout<<(x->data);
        infix(x->right);
        
    }
}
//function for postfix notation
void postfix(node *x)
{
    if (x==NULL)
    return ;
    else
    {
        postfix(x->left);
        postfix(x->right);
        cout<<(x->data);
        
    }
}
//function that converts prefix to binary tree  and show its infix and postfix from the tree itself
void prefixtotree(char prefix[])
{ 
    node*s = NULL;
    buildtree(&s,prefix);
    cout<<"infix expression from the tree is :";infix(s);
    cout<<"\npostfix expression from  the tree is:";postfix(s);
}

int main()
{
   
    cout<<"enter the prefix notation:";
    char prefix[50];
    cin>>prefix;
    prefixtotree(prefix);
    

    return 0;
}