Search code examples
cdata-structuresstackrpn

Infix to reverse polish notation


I am writing a code to convert infix expression to reverse notation but my program is crashing on executing the file

typedef struct stack
 {
   char a[400];
   int top;
 }
 stack;
 stack s;
 void push(char *,int);
 int pop();

 int main()
  {
    char x[400];
    int len,i,y;
    puts("Enter string");
    scanf("%s",x);
    len=strlen(x);
    for(i=0;i<len;i++)
      {
//considering user is entering only the small alphabets 

      if((x[i])>=97&&x[i]<=122)
      printf("%s",x[i]);

      else
//if encountering the operator then pushing it into stack

      if(x[i]=='/'||x[i]=='*'||x[i]=='+'||x[i]=='-')
        {
        push(x,i);
        }

      else if(x[i]=='(')
      continue;
//When encountering the ')' then popping the operator

      else
        {
        y=pop();
        printf("%c",y);
        }
    }

  return 0;
 }

Passing array and its size as argument

void push(char *x,int i)
{
  stack s;
  s.top++;
  s.a[s.top]=x[i];
}

Returning the popped operator on finding out the ")"

int pop()
 {
   stack s;
   int temp;
   temp=s.a[s.top];
   s.top--;
   return temp;
 }

Solution

  • In your code

    printf("%s",x[i]);
    

    is wrong. What you want is

    printf("%c",x[i]);
    

    AS per the C11 standard, chapter 7.21.6.1, %s format specifier

    If no l length modifier is present, the argument shall be a pointer to the initial element of an array of character type. ...

    but here x[i] is of type char.

    Also, from paragraph 9,

    If any argument is not the correct type for the corresponding conversion specification, the behavior is undefined.

    So, your code invokes undefined behaviour.

    Next, for both the functions, push() and pop(), you're defining a local variable stack s; which is created on each call to those functions and destroyed upon finishing execution. You may want to use the gloabl variable instead. Remove the local variables, they are not needed.

    Also, for both the functions, you're using s.top value as the index of s.a array but without any boundary check on the same. You should put a check on the array index value for stack full case (push()) and stack empty case (pop()) before using s.top value as index. The increment and decrement of the s.top should also be placed under the check.


    EDIT:

    For the logical part, after parsing all the inputs, you should chcek if there is any element left on the stack to be popped or not. You should print the stack containts untill the stack becomes empty to get the complete notation. Check my comment below for the idea of a pseudocode.


    Note: As per C standard, int main() should be int main(void)