Search Tutorials

Saturday, 20 April 2013

C code to implement Postfix Expression Tree

/* C program to implement postfix expression tree and calculating its value */

#include<stdio.h>
#include<conio.h>
#include<alloc.h>
#include<stdlib.h>
#include<string.h>

struct tree
{
    char data;
    struct tree *left,*right;
};

int top=-1;
struct tree *stack[20];
struct tree *node;

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

struct tree * pop()
{
    return(stack[top--]);
}

/* Calculating the value of postfix expression using recursion */

int cal(struct tree *node)
{
    int ch;
    ch=check(node->data);
    if(ch==1)
    return node->data-48;
    else if(ch==2)
    {
        if(node->data=='+')
            return cal(node->left)+cal(node->right);
        if(node->data=='-')
            return cal(node->left)-cal(node->right);
        if(node->data=='*')
            return cal(node->left)*cal(node->right);
        if(node->data=='/')
            return cal(node->left)/cal(node->right);
    }
}

/* Displaying all node in order */

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

/* Checking operator and operands */

int check(char ch)
{
if(ch=='+'||ch=='-'||ch=='/'||ch=='*')
return 2;
else
return 1;
}

/* making simple operand node and pushing into stack */

void operand(char b)
{
    node=(struct tree*)malloc(sizeof(struct tree));
    node->data=b;
    node->left=NULL;
    node->right=NULL;
    push(node);
}

/* making operator node than pop-up two nodes from stack and adding into operator node and finally push node into stack  */

void operators(char a)
{
    node=(struct tree*)malloc(sizeof(struct tree));
    node->data=a;
    node->right=pop();
    node->left=pop();
    push(node);
}

void main()
{
    int i,p,k,ans;
    char s[20];
    clrscr();
    printf("Enter the expression in postfix form \n");
    fflush(stdin);
    gets(s);
    k=strlen(s);
    i=0;
    for(i=0;s[i]!='\0';i++)
        {
            p=check(s[i]);
            if(p==1)
            operand(s[i]);
            else if(p==2)
            operators(s[i]);
        }
    ans=cal(stack[top]);
    printf("\nThe value of the postfix expression you entered is %d\n",ans);
    printf("\nThe inorder traversal of the tree is \n");
    inorder(stack[top]);
    getch();
}

/* Output of Postfix Expression Tree Program */

C code to implement Postfix Expression Tree
Output of Postfix Expression Tree Program

For more related to Data Structure see List of Data Structure Programs. If you like this program, Please share and comment to improve this blog.

8 comments:

  1. Replies
    1. Yes Very Owsome

      Delete
    2. This comment has been removed by the author.

      Delete
  2. Interesting post! Is your theme custom made or did you download it from somewhere? A design like yours with a few simple tweeks would really make my post stand out. Please let me know where you got your design. Bless you marketing consultant

    ReplyDelete
  3. Whats up are using Wordpress for your blog platform? I'm new to the blog world but I'm trying to get started and set up my own. Do you need any coding expertise to make your own blog? Any help would be really appreciated! best web design singapore

    ReplyDelete
  4. I'm truly enjoying the design and layout of your website. It's a very easy on the eyes which makes it much more enjoyable for me to come here and visit more often. Did you hire out a developer to create your theme? Exceptional work!digital marketing skills

    ReplyDelete
  5. Wow that was strange. I just wrote an really long comment but after I clicked submit my comment didn't show up. Grrrr... well I'm not writing all that over again. Anyhow, just wanted to say wonderful blog! komodo liveaboard

    ReplyDelete
  6. I'm still learning from you, while I'm trying to reach my goals. I absolutely enjoy reading everything that is posted on your blog.Keep the posts coming. I liked it! singapore snapchat

    ReplyDelete

Back to Top