infix to postfix conversion

[abrarsyed]

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

int precedence(char c)
{
    switch(c)
    {
        case '*':
        case '/':
            return(2);
        case '+':
        case '-':
            return(0);
    }
}

char *to_postfix(char *infix)
{
    char stack[30],postfix[30];
    int i=0,j=0,top=-1;
    while(infix[i]!=NULL)
    {


        if(isalpha(infix[i])||isdigit(infix[i]))
        {
            postfix[j++]=infix[i++];
        }
        else if(infix[i]=='(')
        {
            stack[++top]=infix[i++];
        }
        else if(infix[i]==')')
        {
                while(stack[top]!='(')
            {
                postfix[j++]=stack[top--];
            }

            top--;
            i++;
        }
        else
        {

                    while(top!=-1&&stack[top]!='('&&precedence(infix[i])<precedence(stack[top]))
                    {
                        postfix[j++]=stack[top--];

                    }
                    stack[++top]=infix[i++];

        }
    }
    while(top>-1)
    {
        postfix[j++]=stack[top--];
    }
    postfix[j]=NULL;
    return(postfix);
}

void main()
{

      char infix[30];
      gets(infix);

      puts(to_postfix(infix));
}                   

[abrarsyed]

hello frnds,can u help me with the code above. it doesnt work properly. if i snd an array postfix as an argument to the function to_postfix it works well, but not lyk what i have done in above code...

[Schol-R-LEA]

First off, stop using the SMS abbreviations; no one will take you seriously here if you insist on that sort of thing. Write out clear, complete English sentences, to the best of your ability, please.

Second, while I know it is a picayune point to make, void main() is not valid in a portable C program; the older standard allowed it, but the only really correct form is int main().

On a related note, drop the #include <conio.h> directive - <conio.h> is not a standard header, and you don't use any functions from it in any case.

Finally, never, ever use gets() - it is too dangerous, because it is unbounded and can overrun the buffer you are reading the data into. Please use fgets() in the future.

That having been said: what is the program actually doing, and how is it failing? As it is right now, my C compiler gives three warnings when I compiler the code:

Compiling: C:\Users\Jay\Documents\Programming\postfix.c
C:\Users\Jay\Documents\Programming\postfix.c: In function 'to_postfix':
C:\Users\Jay\Documents\Programming\postfix.c:22:19: warning: comparison between pointer and integer [enabled by default]
C:\Users\Jay\Documents\Programming\postfix.c:54:15: warning: assignment makes integer from pointer without a cast [enabled by default]
C:\Users\Jay\Documents\Programming\postfix.c:55:5: warning: function returns address of local variable [enabled by default]
Linking console executable: C:\Users\Jay\Documents\Programming\postfix.exe
Process terminated with status 0 (0 minutes, 0 seconds)
0 errors, 3 warnings

The last one I suspect is the critical one - you are passing the back the value of postfix, but postfix is a local variable of to_postfix(), which means it won't have a meaningful value after the function returns. Thus, what you are passing back to the calling function is garbage data.

[Schol-R-LEA]

With a bit of extra work, I think you'll find this solves (most) of the issues with your code:

#include<stdio.h>
#include<ctype.h>
#include<string.h>

int precedence(char c)
{
    switch(c)
    {
    case '*':
    case '/':
        return(2);
    case '+':
    case '-':
        return(0);
    }
}

void to_postfix(char *infix, char* postfix)
{
    char stack[30];
    int i=0,j=0,top=-1;
    while(infix[i] != '\0')
    {
        if(isalpha(infix[i]) || isdigit(infix[i]))
        {
            postfix[j++] = infix[i++];
        }
        else if(infix[i] == '(')
        {
            stack[++top] = infix[i++];
        }
        else if(infix[i] == ')')
        {
            while(stack[top] != '(')
            {
                postfix[j++] = stack[top--];
            }
            top--;
            i++;
        }
        else
        {
            while(top != -1 && stack[top] != '(' && precedence(infix[i]) < precedence(stack[top]))
            {
                postfix[j++] = stack[top--];
            }
            stack[++top] = infix[i++];
        }
    }
    while(top>-1)
    {
        postfix[j++] = stack[top--];
    }
    postfix[j] = '\0';
}

int main()
{
    char infix[30], postfix[30];
    fgets(infix, 30, stdin);
    to_postfix(infix, postfix);
    puts(postfix);

    return 0;
}

HTH.

[abrarsyed]

Thank you brother. So does that mean that if i have a local array in a called function i can never return it to calling function...

[Trentacle]

When you declare an array (or any object) within a function, the memory allocated for it has automatic storage duration, meaning that once the name it was declared with goes out of scope, trying to access the memory (via e.g. a persistent pointer, like you have done) results in undefined behavior.

There are three ways to pass arrays around among functions without running into trouble.

1. Declare the array in the calling code and pass a pointer to it to the called function, which merely manipulates its content as opposed to returning something with the return statement. This is probably the most popular method and is how standard library functions like fgets() work.
2. Within the function, use malloc() to reserve space for the array in dynamic memory and return a pointer to the allocated memory. This has the disadvantage that you have to remember to free() the memory when you're done with it.
3. Wrap the array in a struct. Arrays within structs are passed on the stack just like other kinds of objects (i.e., the array doesn't "decay" into a pointer to its first element). This has several disadvantages, notably that it's unnecessarily complicated for simply passing an array, and doesn't work for arrays of unknown size at compile time (except with C99's flexible array members).

So, yeah, pretty much those are your options.

[abrarsyed]

thank you brother.