#include<cstdio>
#include<cstdlib>
#include<string>
#define NMAX 1000
#define EMPTY -1
using namespace std;
struct Stack{
       char data[NMAX];
       int top;
       };
int isEmpty(Stack *s)
    {return (s->top == EMPTY) ? 1 : 0;}
void makeEmpty(Stack *s)
     {s->top=EMPTY;}
void push(Stack *s,char element)
     { if(s->top == (NMAX-1))
        {
                printf("\nSTACK FULL");
        }
        else
        {
                ++s->top;
                s->data[s->top]=element;
        }}       
char pop(Stack *s)
     {char ret=(char)EMPTY;
        if(!isEmpty(s))
        {
                ret= s->data[s->top];
                --s->top;
        }
        return ret;}
int isOperator(char c)
    {if(c=='+'||c=='-'||c=='*'||c=='%'||c=='/') return 1;
     return 0;}
int Prioritate(char c)
    {  int pri = 0;

        if(c == '*' || c == '/' || c =='%')
                pri = 2;
        else
        {
                if(c == '+' || c == '-')
                        pri = 1;
        }
        return pri;}        
   
/*void IfxToPfx(char *infix,char *postfix,int insertspace)     
     {char *i,*p;
      Stack X;
      i=&infix[0];
      p=&postfix[0];
      makeEmpty(&X);
      while(*i)
       {while(*i==' ' || *i== '\t') i++;
        if(isdigit(*i)|| isalpha(*i)) {while(isdigit(*i)|| isalpha(*i)) {*p=*i;p++;i++;}
                         if(insertspace) {*p=' ';p++;}} 
        if(*i=='(') {push(&X,*i);i++;}
        if(*i==')') {char nl=pop(&X);
                      while(nl!='(')
                        {*p=nl;
                         p++;
                         if(insertspace) {*p=' ';p++;}
                         nl=pop(&X);
                                    }
                                    i++;}
       if(isOperator(*i)) 
                {if(isEmpty(&X)) push(&X,*i);
                 else {char nl=pop(&X);
                       while(Prioritate(*i)<=Prioritate(nl))
                        {*p=nl;
                         p++;
                         if(insertspace){*p = ' '; p++;}
                        nl=pop(&X);}
                        push(&X,nl);
                        push(&X,*i);}
                          i++;
                          }   
     while(!isEmpty(&X))
        {char nl=pop(&X);
         *p=nl;
         p++;
         if(insertspace){*p = ' ';p++;}}                                             
         
               
               }
                *p = '\0';
     }*/
void infix2postfix(char* infix, char * postfix, int insertspace)
{
        char *i,*p;
        Stack X;
        char n1;
        makeEmpty(&X);
        i = &infix[0];
        p = &postfix[0];

        while(*i)
        {
                while(*i == ' ' || *i == '\t')
                {
                        i++;
                }

                if( isdigit(*i) || isalpha(*i) )
                {
                        while( isdigit(*i) || isalpha(*i))
                        {
                                *p = *i;
                                p++;
                                i++;
                        }
                        /*SPACE CODE*/
                        if(insertspace)
                        {
                                *p = ' ';
                                p++;
                        }
                        /*END SPACE CODE*/
                }

                if( *i == '(' )
                {
                        push(&X,*i);
                        i++;
                }

                if( *i == ')')
                {
                        n1 = pop(&X);
                        while( n1 != '(' )
                        {
                                *p = n1;
                                p++;
                                /*SPACE CODE*/
                                if(insertspace)
                                {
                                        *p = ' ';
                                        p++;
                                }
                                /*END SPACE CODE*/
                                n1 = pop(&X);
                        }
                        i++;
                }

                if( isOperator(*i) )
                {
                        if(isEmpty(&X))
                                push(&X,*i);
                        else
                        {
                                n1 = pop(&X);
                                while(Prioritate(n1) >= Prioritate(*i))
                                {
                                        *p = n1;
                                        p++;
                                        /*SPACE CODE*/
                                        if(insertspace)
                                        {
                                                *p = ' ';
                                                p++;
                                        }
                                        /*END SPACE CODE*/
                                        n1 = pop(&X);
                                }
                                push(&X,n1);
                                push(&X,*i);
                        }
                        i++;
                }
        }
        while(!isEmpty(&X))
        {
                n1 = pop(&X);
                *p = n1;
                p++;
                /*SPACE CODE*/
                if(insertspace)
                {
                        *p = ' ';
                        p++;
                }
                /*END SPACE CODE*/
        }
        *p = '\0';
}
     
int main()
{ char in[50],post[50];

        strcpy(&post[0],"");
        printf("Enter Infix Expression : ");
        fflush(stdin);
        gets(in);
        infix2postfix(&in[0],&post[0],1);
        printf("Postfix Expression is : %s\n",&post[0]);
system("PAUSE");
        return 0;}