Expression Tree

Algorithm : Expression Tree

1.Creating an expression tree 

createtree(p)
{
Let us consider a postfix expression ‘p’. We have to represent this expression
as an expression tree.
 
Add ‘$’ at the end of ‘p’

item=read a symbol from ‘p’

while(item≠'$')
 {
 if(item=operand)
  {
  t=getnode()
  t->data=item //creating a node with the operand and pushing it. 
  push(t)
  }
 else if(item=operator)  //Two elements from the stack are popped and making
                              them the children, 
                            the operator is pushed after making it a node.
  {
  p1=pop()
  p2=pop()
  t=getnode()
  t->data=item
  t->lchild=p2
  t->rchild=p1
  push(t)
  }
 
 item=read the next symbol
 }

root=pop()            //the last element in the stack should be the root.
                        So it is returned.
return root
}



2.  Evaluating an expression tree
 
evaluate(root)
{
Let us consider an expression tree pointed by the ‘root’ pointer.
 We have to evaluate the tree at ‘root’.

ptr=root
if(ptr≠NULL)
 {
 lptr=ptr->lchild
 rptr=ptr->rchild
 if(lptr->data=operand)
  v1=lptr->data
 else                        //if two operands are found, then by operating them 
                               with the parent operator, the result is returned.
  v1=evaluate(lptr)
 if(rptr->data=operand)
  v2=rptr->data
 else
  v2=evaluate(rptr)
 
op=ptr->data                       //(v1)op(v2) means v1 and v2 are operated.
 return ((v1)op(v2))

 }
}

//In this set of algorithms, we have often used a algorithm called getnode().
This algorithm allocates a node structure in the memory and returns its address
to the variable.Apart from that, several other functions like search(), height(),
push(), pop() etc are used in the program.
They mean the general operations described before.


C Program For Expression Tree

Source Code:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

struct tree
{
 char data;
 struct tree *lchild;
 struct tree *rchild;
};

struct tree * s[30];
int top=-1,tp=-1;
char a[20];

struct tree * gettree()
{
 struct tree *t;
 t=(struct tree *)malloc(sizeof(struct tree));
 t->lchild=NULL;
 t->rchild=NULL;
 return t;
}

void push(struct tree *item)
{

  top=top+1;
  s[top]=item;
}

struct tree * pop()
{
  struct tree *item;
  item=s[top];
  top=top-1;
 return item;
}

void inorder(struct tree *root)
{
   if(root->data=='$')
      printf("\nTree not created");
   else
   {
      if(root!=NULL)
      {
  inorder(root->lchild);
  printf("  %c",root->data);
  inorder(root->rchild);
      }
   }
}

void preorder(struct tree *root)
{
   if(root->data=='$')
      printf("\nTree not created");
   else
   {
      if(root!=NULL)
      {
  printf("  %c",root->data);
  preorder(root->lchild);
  preorder(root->rchild);
      }
   }
}

void postorder(struct tree *root)
{
   if(root->data=='$')
      printf("\nTree not created");
   else
   {
      if(root!=NULL)
      {
  postorder(root->lchild);
  postorder(root->rchild);
  printf("  %c",root->data);
      }
   }
}

int isop(char y)
{
  switch(y)
   {
     case '+':
     case '-':
     case '*':
     case '/':
     case '%':
     case '^':
       return 1;
       break;
     case '{':
     case '[':
     case '(':
     case ')':
     case '}':
     case ']':
       return 2;
       break;
     default:
      return 0;
      break;
   }
}

int pre(char op)
{
  switch(op)
   {
     case '+':
     case '-':
       return 1;
       break;
     case '*':
     case '/':
     case '%':
       return 2;
       break;
     case '^':
       return 3;
       break;
     default:
      return 0;
      break;
   }
}

float operation(float b,float a,char z)
{
  switch(z)
   {
     case '+':
       return b+a;
       break;
     case '-':
       return b-a;
       break;
     case '*':
       return b*a;
       break;
     case '/':
       return (b/a);
       break;
     case '%':
       return ((int )b%(int )a);
       break;
     case '^':
       return pow(b,a);
       break;
    }
}

void pu_sh(char item)
{
     tp=tp+1;
     a[tp]=item;
}

char p_op()
{
  char item;
  item=a[tp];
  tp=tp-1;
  return item;
}

void itop(char e[15],char p[15])
{
  int j,k=0,l,i,g;
  char x,y,m,sym;
  printf("\nEnter an infix expression: ");
  fflush(stdin);
  gets(e);
  l=strlen(e);
  strcat(e,")");
  m='(';
  pu_sh(m);
  i=0;
  while(tp!=-1)
   {
      x=e[i];
      if(isop(x)==0)
       {
  p[k]=x;
  k=k+1;
       }

      else if(x=='(')
       {
  pu_sh(x);
       }

      else if(x==')')
       {
  y=p_op();
  while(y!='(')
   {
     p[k]=y;
     k=k+1;
     y=p_op();
   }
       }

      else if(isop(x)==1)
       {
  y=p_op();
  while(isop(y)==1 && pre(y)>=pre(x))
   {
     p[k]=y;
     k=k+1;
     y=p_op();
   }
  pu_sh(y);
  pu_sh(x);
       }
     i++;
   }
  p[k]='\0';
  puts(p);
}

struct tree * crextree()
{
  struct tree *p1,*p2,*t,*r;
  char sym,e[15],p[15];
  int g;
  itop(e,p);
  strcat(p,"#");
  g=0;
  sym=p[g];
  while(sym!='#')
  {
     if(isop(sym)==0)
     {
 t=gettree();
 t->data=sym;
 push(t);
     }
     else if(isop(sym)==1)
     {
 p1=pop();
 p2=pop();
 t=gettree();
 t->data=sym;
 t->lchild=p2;
 t->rchild=p1;
 push(t);
     }
     g++;
     sym=p[g];
  }
  r=pop();
  return r;
}

float evaluate(struct tree *root)
{
    struct tree *ptr,*lptr,*rptr;
    char op;
    float v1,v2;
    ptr=root;
    if(ptr!=NULL)
    {
       lptr=ptr->lchild;
       rptr=ptr->rchild;
       if(isop(lptr->data)==0)
   v1=(float)(lptr->data)-'0';
       else
   v1=evaluate(lptr);
       if(isop(rptr->data)==0)
   v2=(float)(rptr->data)-'0';
       else
   v2=evaluate(rptr);
       op=ptr->data;
       return operation(v1,v2,op);
    }
}

void main()
{
 int ch,h,c,opt,h1,h2,c1,c2;
 float v;
 struct tree *root,*s,*rt;
 root=gettree();
 root->data='$';
 while(1)
 {
 printf("\n\nExpression tree Operations:");
 printf("\n\t1.Creation\n\t2.Evaluation\n\t3.Traversal\n\t4.Exit");
 printf("\n\nEnter your choice:");
 scanf("%d",&ch);
 switch(ch)
 {
     case 1: root=crextree();
      break;
     case 2: v=evaluate(root);
       printf("\nValue of the expression tree=%g",v);
       break;
     case 3: printf("\n\n\t1.Inorder\n\t2.Preorder\n\t3.Postorder");
      printf("\nEnter Your choice:");
      scanf("%d",&ch);
      switch(ch)
      {
         case 1: printf("\nInorder traversal:\n");
          inorder(root);
          break;
         case 2: printf("\nPreorder traversal:\n");
          preorder(root);
          break;
         case 3: printf("\nPostorder traversal:\n");
          postorder(root);
          break;
      }
      break;

     case 4: exit(0);
 }
 }
}