/***********************************************
  InFix To PreFix & PostFix & Evaluation
  Made By GAURANG
	       Visit
  	gaurang85.tripod.com
                -OR-
	gaurang.cjb.net
 ***********************************************/
#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<math.h>

char op[30],eq[30],eval[30];

int priority(char);
void postfix(),prefix(),evaluate();
int i,j=0,k=0,ch,s,operand[15],opand;

int main()
{
A:
clrscr();
flushall();
printf("\t\t\tMENU");
printf("\n\t\t1. In-Fix To Post-Fix");
printf("\n\t\t2. In-Fix To Pre-Fix");
printf("\n\t\t3. Evaluation");
printf("\n\t\t4. Quit");
printf("\n\t\t::>");
scanf("%d",&s);
if(s==4)return 0;
printf("\nEnter Equation : ");
scanf("%s",eq);
switch(s)
{
case 1:
	postfix();
	goto A;
case 2:
	prefix();
	goto A;
case 3:
	j=0;
	for(i=0;i<strlen(eq);i++)
	{
		if(priority(eq[i])==8)
		{
			printf("\nEnter Values Of %c : ",eq[i]);
			scanf("%d",&operand[j]);j++;
		}
	}
	postfix();k=0;
	evaluate();
	getch();
	goto A;
case 4:
	return 0;
default:
	goto A;
}
//return 0;
}

void postfix()
{
printf("\nPost Fix Equation \n");
j=0; //make stack point to zero
for(i=0;i<strlen(eq);i++)
{
 ch=priority(eq[i]);
 if(ch==8)
 {
  printf("%c",eq[i]);
  eval[k]=eq[i];
  k++;
  opand++;
 }
 else
 {
  if(j==0)	//if 1st element then push into stack
  {
   op[j]=eq[i];
   j++;
  }
  else
  {
   if(ch==7)	//check for closing brakets
   {
    while(op[j-1]!='(')
    {
     eval[k]=op[j-1];
     k++;
     printf("%c",op[j-1]);
     j--;
    }
    j--;
   }
   else
   {
    if(ch>priority(op[j-1]))
    {
     op[j]=eq[i];
     j++;
    }
    else
    {
     if(op[j-1]=='(')
     {
      op[j]=eq[i];
      j++;
     }
     else
     {
      if(ch<priority(op[j-1]))
      {
       while(ch<=priority(op[j-1])&&op[j-1]!='('&&j!=0)
       {
	eval[k]=op[j-1];
	k++;
	printf("%c",op[j-1]);
	j--;
       }
       op[j]=eq[i];
       j++;
      }
     }
    }
   }
  }
 }
}
while(j!=0)
{
 if(op[j]!='(')
 {
  eval[k]=op[j-1];
  k++;
  printf("%c",op[j-1]);
 }
 j--;
}
getch();
}

void prefix()
{
printf("\nPre Fix Equation \n");
j=0; //make stack point to zero
strrev(eq);
for(i=0;i<strlen(eq);i++)
{
   ch=priority(eq[i]);
   if(ch==8)
   {
      //printf("%c",eq[i]);
      eval[k]=eq[i];
      k++;
      opand++;
   }
   else
   {
      if(j==0)	//if 1st element then push into stack
      {
	 op[j]=eq[i];
	 j++;
      }
      else
      {
	 if(ch==6)	//check for opening brakets
	 {
	    while(op[j-1]!=')')
	    {
	       eval[k]=op[j-1];
	       k++;
	       //printf("%c",op[j-1]);
	       j--;
	    }
	    j--;
	 }
	 else
	 {
	    if(ch>priority(op[j-1]))
	    {
	       op[j]=eq[i];
	       j++;
	    }
	    else
	    {
	       if(op[j-1]==')')
	       {
		  op[j]=eq[i];
		  j++;
	       }
	       else
	       {
		  if(ch<priority(op[j-1]))
		  {
		     while(ch<=priority(op[j-1])&&op[j-1]!=')'&&j!=0)
		     {
			eval[k]=op[j-1];
			k++;
			//printf("%c",op[j-1]);
			j--;
		     }
		     op[j]=eq[i];
		     j++;
		  }
	       }
	    }
	 }
      }
   }
}
while(j!=0)
{
   if(op[j]!='(')
   {
      eval[k]=op[j-1];
      k++;
      //printf("%c",op[j-1]);
   }
   j--;
}
strrev(eval);
printf("\n%s",eval);
getch();
}

void evaluate()
{
char opan;
int ans,one,two;
i=0;j=0;k=0;ch=0;
//if(strlen(eval)==3)ch==0;
while(ch==0)
{
if((priority(eval[i])==8)&&(priority(eval[i+1])==8)&&(priority(eval[i+2])!=8))
{
	one=operand[k];k++;
	two=operand[k];k++;
	if(eval[i+2]=='+')ans=one+two;
	else if(eval[i+2]=='-')ans=one-two;
	else if(eval[i+2]=='*')ans=one*two;
	else if(eval[i+2]=='/')ans=one/two;
	else if(eval[i+2]=='^')ans=pow(one,two);
	//opan=ans;eval[i]=opan;
	operand[k-2]=ans;one=k-1;
	while(k<opand)
	{
		operand[one]=operand[k];
		one++;k++;
	}
	opand--;
	j=i+3;
	i++;
	if(opand!=1)
	{
		while(eval[j]!='\0')
		{
			eval[i]=eval[j];
			j++;i++;
		}
		eval[i]='\0';
		evaluate();
	}
	else
	{
		printf("\n\nANSWER : %d",ans);
		ch=1;
	}
}
else
{
	i++;k++;
}
}
}



int priority(char c)
{
if(c=='+')return 1;
else if(c=='-')return 2;
else if(c=='*')return 3;
else if(c=='/')return 4;
else if(c=='^')return 5;
else if(c=='(')return 6;
else if(c==')')return 7;
else return 8;
}