Expression Tree using Postfix Expression

#include <stdio.h>
#include <malloc.h>

typedef struct node
{
    char data;
    struct node *left,*right;
}node;

node *stack[50];
int top=-1;

void push(node *val)
{
    top++;
    stack[top]=val;
}

node* pop()
{
    node *ele;
    if(top==-1)
        return NULL;
    ele = stack[top];
    top--;
    return ele;
}

void inorder(node *T)
{
    if(T!=NULL)
    {
        inorder(T->left);
        printf("%c",T->data);
        inorder(T->right);
    }
}

int main()
{
    char c;
    node *tt,*t1,*t2;
    tt=NULL;
    printf("Enter postfix expression ");
    while((c=getchar())!='\n')
    {
        if(isalpha(c))
        {
            tt=(node*)malloc(sizeof(node));
            tt->left=NULL;
            tt->right=NULL;
            tt->data=c;
            push(tt);
        }
        else
        {
            t2=pop();
            t1=pop();
            tt=(node*)malloc(sizeof(node));
            tt->data=c;
            tt->left=t1;
            tt->right=t2;
            push(tt);
        }
    }
    printf("Inorder expression ");
    inorder(tt);
    return 0;
}

/*Output
Enter postfix expression AB*C+
Inorder expression A*B+C
*/

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s