INFIX to POSTFIX conversion

CodeProject

#define MAX 255

struct list

{

    char c;                     //store a character here

    struct list *prev;          //pointer to previou element

};

struct stack

{

    struct list *top;           //stack top pointer

    struct list *start;         //stack start(base) pointer

};

void push(struct stack *top,char c);

void pop(struct stack *top, char *c);

void push(struct stack *stk, char c)

{

    struct list *temp;

    temp = (struct list*)malloc(1*sizeof(struct list));

    temp->c = c;

    temp->prev = stk->top;

    stk->top = temp;

}

void pop(struct stack *stk,char *c)

{

    struct list *temp;

    *c = stk->top->c;

    temp = stk->top;

    stk->top = temp->prev;

    free(temp);

}

//precedence function for operators

int prec(char a);

char* to_postfix(char *str)

{

    struct stack stk;

    char post[MAX],*p,ch,*backup;

    //post[] is a string that will have post fix string

    //p is pointer to it.

    //backup is a pointer to input string that will be user later to copy post[] to *str

    p = post;

    backup = str;

    //create a stack

    stk.start = (struct list*)malloc(1*sizeof(struct list));

    //initially start == top

    stk.top = stk.start;

    //since no item is in stack prev of both top & stack is NULL

    stk.start->prev = NULL;

    stk.top->prev = NULL;

    while(*str!='\0')

    {

        //if operand add it to o/p string

        if( isalnum(*str) )

            *p++ = *str++;

        else if(*str == '(' || *str == '+' || *str == '-' || *str == '*' || *str == '/')

        {

            //if '(' push it directly

            if( *str == '(' )

                push(&stk,*str++);

            //push higher precedence operator

            else if( stk.start==stk.top || (prec(*str) > prec(stk.top->c)))

                push(&stk,*str++);

            else

            {

                //pop operators from stack till we get lesser precedence operator or empty stack

                while( ( prec(*str) <= prec(stk.top->c) ) && (stk.top != stk.start) )

                    pop(&stk,p++);

                //now push current opreator from i/p string

                push(&stk,*str++);

            }

        }

        //if closing bracket in input string encountered

        else if(*str == ')' )

        {

            //then while we encounter opening bracket or reach start of stack

            while(stk.top != stk.start)

            {

                if(stk.top->c == '(')

                {

                    //just pop ')' in a dummy variable and break out of loop

                    pop(&stk,&ch);

                    break;

                }

                else

                    //keep popping operators and adding to o/p string if '(' not found

                    pop(&stk,p++);

            }

            //check that last item popped was a matching '('

            if(ch != '(')

            {

                printf("\nERROR: ')' NOT MATCHED...EXITING\n");

                exit(1);

            }

            //go to next char in input string on matching ')'

            str++;

        }

        //ignore white spaces

        else if(*str == ' ' || *str == '\t')

            str++;

        //if unexpected operator then exit

        else

        {

            printf("\n\nERROR : \"%c\" -> WRONG INPUT...EXITING\n",*str);

            exit(1);

        }

    }

    //now pop any remaing opeartors in stack and add them to o/p string

    while(stk.top != stk.start)

    {

        pop(&stk,p);

        //check that last item popped was a matching '('

        //if so then we have extra '('

        if(*p == '(')

        {

            printf("\nERROR: '(' NOT MATCHED...EXITING\n");

            exit(1);

        }

        p++;

    }

    *p = '\0';

    //now we need to copy because post[] is destroyed and can be overwritten

    //as soon as we return from this function

    strcpy(backup,post);

    return backup;

}

int prec(char a)

{

    //make '(' lowest precedence so that it is not popped by any other opeartor

    if(a=='(')

        return 1;

    if(a == '+' || a == '-')

        return 2;

    else if (a == '/' || a == '*')

        return 3;

    return 0;

}