Program to find the expression tree.

Expression tree is a tree consisting of the operands at the leaf node, and the operators at the inner nodes. This Program is part of DATA STRUCTURE.


#include"stdio.h"
#include"conio.h"
#include"process.h"
#include"string.h"
#include"stdlib.h"

struct treenode
{
char c;
treenode * rlink;
treenode * llink;
}*stc[30],*temp,*root;


char prefix[20],ch;
int topt=-1,max=50,len; //global declaration

void pusht(struct treenode * p);
struct treenode* popt();
void tredis(struct treenode *ptr,int level);
void exptree();
void post(struct treenode* p);

void main()
{
clrscr();
printf("Enter a prefix expression :");
scanf("%s",prefix);
exptree();
tredis(root,1);
printf("The postfix expression is :");
post(root);
getch();
}

void post(struct treenode* p)
{
if(p!=NULL)
{
post(p->llink);
post(p->rlink);
printf("%c",p->c);
}
}
void exptree()
{
len=strlen(prefix);
int i=len-1;
while(i>=0)
{
switch(prefix[i])
{
case '+':
case '-':
case '*':
case '/':
case '^':
temp=(struct treenode*)malloc(sizeof(struct treenode));
temp->c=prefix[i];
temp->llink=popt();
temp->rlink=popt();
pusht(temp);
break;
default :
temp=(struct treenode*)malloc(sizeof(struct treenode));
temp->c=prefix[i];
temp->rlink=NULL;
temp->llink=NULL;
pusht(temp);
}
i--;
}
root=stc[topt];
}


void pusht(struct treenode * p)
{
if(topt==max)
{
printf("*@@ Capacity*@@*");
}
else
{
stc[++topt]=p;
}
}


struct treenode* popt()
{
if(topt==-1)

printf("/**@ Expression@**/");

else

return(stc[topt--]);

}
void tredis(struct treenode *ptr,int level)
{
int i;
if ( ptr!=NULL )
{
tredis(ptr->rlink, level+1);
printf("");
for (i = 0; i < level; i++)
printf(" ");
printf("%c", ptr->c);
tredis(ptr->llink, level+1);
}
}