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
