Evaluation of Binary Expression Tree

Evaluation of Expression Tree

#include<stdio.h>

#include<malloc.h>

#include<math.h>

#include<ctype.h>

struct node

{

            char data;

            struct node *lchild;

            struct node *rchild;

};

typedef struct node * NODE;

NODE getnode()

{

    NODE x;

    x = (NODE)malloc(sizeof(struct node));

    x->lchild =NULL;

    x->rchild = NULL;

    return x;

}

NODE create_tree(char postfix[])

{

            NODE temp, s[70];

            char symb;

            int i, top = -1;

            for(i=0; postfix[i] != '\0' ; i++)

            {

                        symb = postfix[i] ;

                        temp = getnode();

                        temp->data = symb;

                        if(isalnum(symb))

                        {

                                                s[++top] = temp;    //push operand to the stack

                        }

                        else

                        {

                                                temp->rchild = s[top--];    //pop second operand from stack and make it rchild

                                                temp->lchild = s[top--];    // pop first operand from stack and make it lchild

                                                s[++top] = temp;            //push operator node to stack

                        }

            }

            return s[top--];        //return the root of expression tree

}

float evaluate(NODE root)

{

            float num;

            switch(root->data)

            {

                        case '+': return evaluate(root->lchild)+evaluate(root->rchild);

                        case '-': return evaluate(root->lchild)-evaluate(root->rchild);

                        case '*': return evaluate(root->lchild)*evaluate(root->rchild);

                        case '/': return evaluate(root->lchild)/evaluate(root->rchild);

                        case '^':

                        case '$': return  pow(evaluate(root->lchild),evaluate(root->rchild));

                        default: if(isalpha(root->data))

                                    {

                                                printf("\n%c = ", root->data);

                                                scanf("%f", &num);

                                                return num;

                                    }

                                    else

                                                return root->data  - '0';

            }

}

void main()

{

            char postfix[60];

            float res;

            NODE root = NULL;

            printf("\nEnter the postfix expression: ");

            scanf("%s", postfix);

            root = create_tree(postfix);

            res = evaluate(root);

            printf("\nResult of expression is = %f", res);

}

Output:

Case 1:

Enter the postfix expression: 632-5*+1^7+

Result of expression is = 18.000000

Case 2:

Enter the postfix expression: abc-d*+e^f+

e = 1

a = 6

b = 3

c = 2

d = 5

f = 7

Result of expression is = 18.000000