EX.NO: 5 IMPLEMENTATION OF EXPRESSION TREE
AIM:
To write a c program to implement an expression tree and produce its inorder, preorder and postorder traversal.
ALGORITHM:
Step 1: Start the program.
Step 2: Include the header files.
Step 3: Enter the postfix expression as input.
Step 4: Select i for infix, o for postfix, r for prefix.
Step 5: Scan the expression if operands create one node tree and push a
pointer onto the stack.
Step 6: If the scanned is an operator two top most pointers in stack are
popped T1 and T2 and form a new tree whose root is the operator
and whose left and right child points to T2 and T1 respectively.
Step 7: print the results.
Step 8: Stop the program.
PROGRAM:
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define operator 1
#define notoperator 0
#define empty -1
int chkelement(char);
void opfunc(char);
void varfunc(char);
void push(struct node*);
struct node* pop(void);
void disptree(void);
void infix(struct node*);
void prefix(struct node*);
void postfix(struct node*);
char equation[25];
struct node* stack[25];
int stackptr=-1;
struct node
{
char item;
struct node* leftchild;
struct node* rightchild;
};
struct node* root;
void main(void)
{
int count;
clrscr();
printf("Implementation of expr tree");
printf("\nEnter postfix expr:");
gets(equation);
for(count=0;equation[count]!='\0';count++)
{
switch(chkelement(equation[count]))
{
case operator:opfunc(equation[count]);
break;
case notoperator:varfunc(equation[count]);
break;
default:printf("\nunrecognised entry");
}
}
disptree();
getch();
}
void disptree(void)
{
char choice;
while(1)
{
printf("\nselect the o/p form:[i]nfix,p[r]efix,p[o]stfix");
choice=getch();
switch(choice)
{
case 'i':printf("\ninfix rep of o/p is:");
infix(stack[stackptr]);break;
case 'r':printf("\nprefix rep of o/p is:");
prefix(stack[stackptr]);break;
case 'o':printf("\npost order rep of o/p is:");
postfix(stack[stackptr]);break;
default:printf("\n wrong choice");exit(0);
}
}
}
void infix(struct node* root)
{
if(root->leftchild!=NULL)
infix(root->leftchild);
printf("%c",root->item);
if(root->rightchild!=NULL)
infix(root->rightchild);
}
void prefix(struct node* root)
{
printf("%c",root->item);
if(root->leftchild!=NULL)
prefix(root->leftchild);
if(root->rightchild!=NULL)
prefix(root->rightchild);
}
void postfix(struct node* root)
{
if(root->leftchild!=NULL)
postfix(root->leftchild);
if(root->rightchild!=NULL)
postfix(root->rightchild);
printf("%c",root->item);
}
void opfunc(char optr)
{
root=(struct node*)malloc(sizeof(struct node));
root->item=optr;
root->rightchild=pop();
root->leftchild=pop();
push(root);
}
struct node* pop(void)
{
return(stack[stackptr--]);
}
void varfunc(char var)
{
root=(struct node*)malloc(sizeof(struct node));
root->item=var;
root->rightchild=NULL;
root->leftchild=NULL;
push(root);
};
void push(struct node* root)
{
stack[++stackptr]=root;
}
int chkelement(char element)
{
switch(element)
{
case '+':
case '-':
case '*':
case '/':
case '%':
case '^':return(operator);
default:return(notoperator);
}
}
