Postfix Evaluation

Algorithm : Postfix Evaluation
 
Postfix_Evaluation(P[1,2,...,N],S[1,2,...,N],top)
{
  Let us consider a postfix expression 'P'. We have to evaluate the 
  value of P using a stack,’S’ with top ‘t’ and capable of holding N 
  elements.Push and Pop operation is done on the top of ‘S’.

1. Insert a symbol '$' at the end of P.
2. x=Read a symbol from P
3. while(x≠'$')                       //until it reaches the end of P
   {
   if(x=operand)
	push(x)
   else
	{
	A=pop()                        //2nd operand is popped
	B=pop()                        //1st operand is popped       
	C=B(op)A                       //operation is done b/w A and B      	
        push(C)                        //resultant value is stored into ‘S’
	}
   x=Read a symbol from P
   }
4. Value=pop()
5. print “Value”
6. End
}


C Program For Postfix Evaluation

Source Code:

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

float s[10];
int top=-1;



void push(float item)
{

 if(top==9)
   {
     printf("\nStack overflow");
   }
 else
   {
     top=top+1;
     s[top]=(float)item;
   }
}


float pop()
{
  float item=-1;
  if(top==-1)
   {
     printf("\nStack Underflow");

   }
  else
   {
     item=s[top];
     top=top-1;
   }
  return item;
}

void show()
{
int i;
printf("\nStack");
for(i=0;i<=top;i++)
printf("\t%g",s[i]);

}
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;
    }
}

float posteva(char p[10])
{
 int i;
  float val,a,b,c;
 char d[10],y;
 strcpy(d,p);
 strcat(d,"$");
 i=0;
 while(d[i]!='$')
 {
   y=d[i];
   
   if(isop(y)==0)
   {
    push((float)y-'0');
   }
   else
   {
    a=pop();
    b=pop();
    c=operation(b,a,y);
    push(c);
   }
   show();
   i++;
  }
  val=pop();
  return val;
}

void main()
{
  int j,k=0,l,i,w;
  char e[15],p[15],x,y,m;
  float r;
 
  printf("\nEnter an infix expression: ");
  gets(e);
  l=strlen(e);
  strcat(e,")");
  m='(';
  push(m);
  i=0;
  while(top!=-1)
   {
      x=e[i];
      if(isop(x)==0)
       {
	 p[k]=x;
	 k=k+1;
       }

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

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

      else if(isop(x)==1)
       {
	 y=pop();
	 while(isop(y)==1 && pre(y)>=pre(x))
	  {
	    p[k]=y;
	    k=k+1;
	    y=pop();
	  }
	 push(y);
	 push(x);
       }
     i++;
   }
  p[k]='\0';
  printf("\nThe postfix expression is :  ");
  puts(p);
  printf("\nDo you want to get its value ?");
  printf("\n 1.Yes  2.No ");
  printf("\nEnter your choice:");
  scanf("%d",&w);
  switch(w)
  {
   case 1:
	 r=posteva(p);
	 printf("\nvalue=%g",r);
	 break;
   case 2:
	  break;
  }

}


 OUTPUT 1:
Enter an infix expression: (4+7)-(5*9)/3

The postfix expression is :  47+59*3/-

Do you want to get its value ?
 1.Yes  2.No
Enter your choice:1

Stack   4
Stack   4       7
Stack   11
Stack   11      5
Stack   11      5       9
Stack   11      45
Stack   11      45      3
Stack   11      15
Stack   -4
value=-4
----------------------------------------

 OUTPUT 2:
The postfix expression is :  65/4-37*+

Do you want to get its value ?
 1.Yes  2.No
Enter your choice:1

Stack   6
Stack   6       5
Stack   1.2
Stack   1.2     4
Stack   -2.8
Stack   -2.8    3
Stack   -2.8    3       7
Stack   -2.8    21
Stack   18.2
value=18.2