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.

10 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
  7. This is really interesting, You are a very skilled blogger. I have joined your rss feed and look forward to seeking more of your fantastic post. Also, I have shared your web site in my social networks!
    singapore internet marketing agency

    ReplyDelete
  8. This design is incredible! You obviously know how to keep a reader amused. Between your wit and your videos, I was almost moved to start my own blog (well, almost...HaHa!) Wonderful job. I really enjoyed what you had to say, and more than that, how you presented it. Too cool!
    online marketing firm singapore

    ReplyDelete

Back to Top