//Program: To convert given infix expression to equivalent postfix form
//Author: Deependra

#include <stdio.h>
#include <string.h>
#define TRUE 1
#define FALSE 0
#define MAXSIZE 30              //Maximum size of stack

int top=-1;                     //Initializing top of stack

/*Main Program*/
int main()
{
        char str[40],op[]={'^','*','/','+','-'},stack[MAXSIZE],out;
        int i,j,k,flag;

        void push(char ,char []);
        char pop(char []);
        int priority(char);

        printf("Enter the infix expression : ");
        fgets(str,sizeof(str),stdin);

        for(i=0;i<strlen(str)-1;i++)
        {
                flag=FALSE;
                for(j=0;j<5;j++)
                {
                        if(str[i]==op[j])
                        {
                                flag=TRUE;
                                if(top==-1)
                                {
                                        push(str[i],stack);
                                }
                                else
                                {
                                        for(k=top;k>=0;k--)
                                        {
                                                if(priority(stack[k])>priority(str[i]))
                                                {
                                                        out=pop(stack);
                                                        printf("%c",out);
                                                        if(top==-1)
                                                        {
                                                                push(str[i],stack);
                                                                break;
                                                        }
                                                }
                                                else if(priority(stack[k])<priority(str[i]))
                                                {
                                                        push(str[i],stack);
                                                }
                                                else if(priority(stack[k])==priority(str[i]))
                                                {
                                                        out=pop(stack);
                                                        printf("%c",out);
                                                        if(top==-1)
                                                        {
                                                                push(str[i],stack);
                                                                break;
                                                        }
                                                }
                                        }
                                }
                                break;
                        }
                }
                if(!flag)
                {
                        printf("%c",str[i]);
                }
        }
        if(top!=-1)
        {
                for(k=top;k>=0;k--)
                {
                        out=pop(stack);
                        printf("%c",out);
                }
        }
        printf("\n");
        return 0;
}
/*Push element into stack*/
void push(char element,char stack [])
{
        if(top==MAXSIZE)
        {
                printf("Stack overflow!\n");
                return;
        }
        top=top+1;
        stack[top]=element;
}
/*Pop element out of stack*/
char pop(char stack[])
{
        char element;
        if(top==-1)
        {
                printf("Stack underflow!\n");
                return;
        }
        element=stack[top];
        top=top-1;
        return element;
}
/*Return the priority of operator*/
int priority(char element)
{
        if(element=='^')
        {
                return 3;
        }
        else if(element=='*' || element=='/')
        {
                return 2;
        }
        else if(element=='+' || element=='-')
        {
                return 1;
        }
        return 0;
}