//===================================================================
/*
	ASSIGNMENT no 3 DATA STRUCTURES
	Infix to Postfix

	BY : MUDASSAR RAZA
	     MCS-2

	SUBMIT TO : SIR SHARIF
*/
//==============header files==========================================

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

#define MAX 20
int top=0;
char pop(char []);
void push(char [],char);
int prcd(char,char);
int isoperand(char);
int isoperator(char);
//==============main function=========================================

void main()
  {
     int length,position,j;
     char stack[MAX]={NULL};
     char symbol;
     char infix[MAX]={NULL};
     char postfix[MAX]={NULL};
     int toppost=0;
     clrscr();
     printf("\nenter infix expression");
     scanf("%s",infix);
     length=strlen(infix);
     if(length)
      {
//       push(stack,'(');
  //     strcat(infix,")");
    //   length++;
      for(position=0;position<length;position++)
	 {
	      if(isoperand(infix[position]))
		  postfix[toppost++]=infix[position];
	      else if(isoperator(infix[position]))
		{           symbol=infix[position];
		  while((top>1)&&(prcd(stack[top-1],symbol))&&(isoperator(stack[top-1])))
		       postfix[toppost++]=pop(stack);
		  push(stack,symbol);
		}//else
      //	      else if(infix[position]=='(')
	//	   push(stack,'(');
	 //     else if(infix[position]==')')
	  //	{
	    //	   while(stack[top-1]!='(')
	      //	       postfix[toppost++]=pop(stack);
	       //	}
	      else
		{
		  printf("\ninvalid symbol\n");
		  getch();
		  exit(1);
		}
	 } //for
      while(stack[top-1]!='(')
	postfix[toppost++]=pop(stack);
      postfix[toppost]=NULL;
      printf("postfix expression is == %s",postfix);
      }//if
     getch();
  }
void push(char s[],char item)
  {
    if(top>=MAX)
      {
       printf("\nstack is full\n");
       return;
      }
    s[top]=item;
    top=top+1;
  }
char pop(char s[])
  {
    if(top<=0)
     {
       printf("\nstack underflow\n");
       return -1;
     }
    s[top]=NULL;
    top=top-1;
    return s[top];
  }
int isoperator(char ch)
  {
      int a=0;
      switch(ch)
	{
	 case'+':
	 case'-':
	 case'*':
	 case'/':
	 case'%':
	 case'(':
	 case')':
	 case'^': a=1; break;
	}
      return a;
  }
int isoperand(char ch)
 {
   return((ch>='a' && ch<='z')||(ch>='A' && ch<='Z') || (ch>='0' && ch<='9'));
 }
/*int prcd_level(char ch)
{
     if ( ch == '+' || ch == '-' )
	  return 1;
     else if ( ch == '^' )
	  return 3;
     else
	  return 2;
}
int prcd(char op1,char op2)
 {
     if ( prcd_level(op1) >= prcd_level(op2) )
	  return 1;
     else if ( prcd_level(op1) < prcd_level(op2) )
	  return 0;
 }*/


int prcd(char stktop,char op)
{
 if(((stktop=='+')||(stktop=='-'))&&((op=='*')||(op=='/')))
   {
    return(0);
   }
 if(stktop=='(')
   {
    return(0);
   }
 if((stktop!=')')&&(op=='('))
   {
    return(0);
   }
 if((stktop!='(')&&(op==')'))
   {
    return(1);
   }
}