Infix to prefix problem

[gaurav_13191]

I have written the following code for converting infix to prefix..

//Infix to prefix conversion

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

#define MAX 25

void initstack(struct stack *);
void push(struct stack *,char);
char pop(struct stack *);
char *convert(struct stack *,char *);
void show(struct stack);
int priority(char);

struct stack
{
 char arr[MAX];
 int top;
};

int main()
{
 struct stack p;
 char *str1,*str3,a[10],b[10];
 str1=a;
 str3=b;
 clrscr();
 printf("\nEnter the expression in infix form:");
 gets(str1);
 str3=strrev(str1);
 puts(str3);
 initstack(&p);                //initialising stack elements
 str1=convert(&p,str3);        //converting infix to prefix
 while(*str1!='\0')
 {
 printf("%c",*str1);
 str1--;
 }
 getch();
 return 0;
}

void initstack(struct stack *s)
{
 s->top=-1;

}

void push(struct stack *s,char data)           //pushing data on stack
{
 if(s->top==MAX-1)
  printf("\nStack is full");
 else
 {
  ++(s->top);
  s->arr[s->top]=data;
 }
}

char pop(struct stack *s)                      //popping data from stack
{
 char value;
 if(s->top==-1)
 {
  printf("\nStack is empty..nothing to pop");
  return NULL;
 }
 else
 {
  value=s->arr[s->top];
  s->top--;
  return value;
 }
}

char *convert(struct stack *s,char *str2)         //converting str2 into prefix
{
 char *t,opr,g[MAX];
 g[0]='\0';                                       //Null added at g[0]
 t=&g[1];
 while((*str2)!='\0')
 {
  if(isdigit(*str2)||isalpha(*str2))
  {
   while(isdigit(*str2)||isalpha(*str2))
   {
   *t=*str2;
   t++;
   str2++;
   }
  }
  else if(*str2==')')
  {
   push(s,*str2);
   str2++;
  }
  else if(*str2=='+'||*str2=='*'||*str2=='-'||*str2=='/'||*str2=='$'||*str2=='%')
  {
   if(s->top==-1)
    push(s,*str2);
   else
    {
      opr=pop(s);
      while(priority(opr)>priority(*str2))
      {
       *t++=opr;
       opr=pop(s);
      }
      push(s,opr);
      push(s,*str2);
    }
    str2++;
  }
  else if(*str2=='(')
  {
   opr=pop(s);
   while(opr!=')')
   {
   *t++=opr;
   opr=pop(s);
   }
   str2++;
  }
 }
 while(s->top!=-1)
 {
  opr=pop(s);
  *t=opr;
  t++;
 }
 t--;
 return t;
}

int priority(char c)                          //assigns priority to operators
{
 if(c=='$')
  return 3;
 else if(c=='*'||c=='/'||c=='%')
  return 2;
 else if(c=='+'||c=='-')
  return 1;
 else
  return 0;
}

I will explain my program a bit so that it is not a problem for others.
Firstly,the expression has been taken as input from user in infix notation and stored in str1, and the expression is then reversed and stored in str3. str3 is then passed to the convert function along with stack p which has been initialized earlier.Now, in the convert function, a char array g has been taken with its first element initialised to null('\0'),and a character pointer is used to store the elements in the order which are in reverse prefix form..(eg A+B would give BA+ in g)and at last t is pointing to the first element of the prefix expression.After that, t is returned and characters are printed while null does not occur.

My input: A+B
Output:B+A
+

The error is in the second line of output which should be +AB instead of +

I have not taken care of spaces in this program so take only the input given below and correct it accordingly.
I am using Turbo C as compiler.Please help!!

[Schol-R-LEA]

I'll look over the code and see if I can find anything that stands out but there is one thing I can say: you would be wise to use fgets(str1, 10, stdin) with instead of gets(str1) , as gets() can all too easily have a buffer overrun and crash the program. The gets() function has been consider deprecated for some time now, though it presumably isn't getting removed from the standard I/O library for reasons of backward compatibility.

As I said, I'll try to find something more relevant to the problem at hand.

[Schol-R-LEA]

I found two serious problems with the convert() function. First, you are returning a pointer into a local variable, a variable which is likely to be partially or wholly overwritten by the time you are trying to print it. The solution to this is to one more character buffer and pass that as an argument to convert(); even if the buffer is not used directly, it will hold the data even after the convert() function ends, allowing you to use pointers to walk through it.

More seriously, the function does not address whitespace characters at all. This is a serious problem, because even if you haven't deliberately added any whitespace, the fgets() function will read in the trailing newline character, meaning that the whole function stalls out. Adding another clause to the function to test for spaces and newlines, and walking past them, appears to fix the problems you are experiencing.

char *convert(struct stack *s,char *source, char* dest)  //converting source into prefix
{
    char *t,opr;
    dest[0]='\0';                              //Null added at end of dest
    t=&dest[1];
    while((*source)!='\0')
    {
        if(*source == ' ' || *source == '\n')
        {
            source++;
        }
        else if(isdigit(*source)||isalpha(*source))
        {
            while(isdigit(*source)||isalpha(*source))
            {
                *t=*source;
                t++;
                source++;
            }
        }
        else if(*source==')')
        {
            push(s,*source);
            source++;
        }
        else if(*source=='+'||*source=='*'||*source=='-'||*source=='/'||*source=='$'||*source=='%')
        {
            if(s->top==-1)
                push(s,*source);
            else
            {
                opr=pop(s);
                while(priority(opr)>priority(*source))
                {
                    *t++=opr;
                    opr=pop(s);
                }
                push(s,opr);
                push(s,*source);
            }
            source++;
        }
        else if(*source=='(')
        {
            opr=pop(s);
            while(opr!=')')
            {
                *t++=opr;
                opr=pop(s);
            }
            source++;
        }
    }
    while(s->top!=-1)
    {
        opr=pop(s);
        *t=opr;
        t++;
    }
    t--;
    return t;
}

I've only tested this with some simple cases, so I don't know if it works across the board, but it does at least work for the A+B case you mentioned.

You also never wrote a show() function, something I remedied while testing convert():

void show(struct stack *s)
{
    int i;

    printf("Stack: ");
    for (i = 0; i <= s->top; i++)
    {
        putchar(s->arr[i]);
        if (i < s->top)
        {
            putchar(',');
        }
    }
    putchar('\n');
}