below is the code of infix to postfix conversion using stack.The code executes an infinite loop printing stack underflow in one of the pop function ,i have tried commenting pop function call in right paranthesis loop but then there is no output, i am unable to find which pop function creates this problem . if anyone could help me find what the problem is it would be appreciated.

P.S. - The code works fine if i remove parenthesis from the infix equation that i am passing.

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

struct stack{
    int size;
    int top;
    char *arr;
};

void display(struct stack *ptr)
{
    if(ptr->top == -1)
    {
        printf("Stack is Empty");
    }
    
    else
    {
        for(int i = ptr->top ; i>=0 ; i--)
        {
            printf("Element: %d\n",ptr->arr[i]);
            
        }
    }
}

int isEmpty(struct stack *ptr)
{
    if(ptr->top == -1)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

int isFull(struct stack *ptr)
{
    if(ptr->top == ptr->size - 1)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

void push(struct stack *ptr,int data)
{
    if(isFull(ptr))
    {
        printf("Stack Overflow");
    }
    else
    {
        ptr->top = ptr->top   1;
        ptr->arr[ptr->top] = data;
    }    
}

char pop(struct stack *ptr)
{
    if(isEmpty(ptr))
    {
        printf("Stack Underflow");
        return 0;
    }
    else
    {
        char ch = ptr->arr[ptr->top];
        ptr->top = ptr->top - 1;
        return ch;

    }    
}

char stackTop(struct stack *ptr)
{
    return ptr->arr[ptr->top];
}

int isOperator(char a)
{
    if(a == ' '|| a == '-'|| a == '*'|| a == '/')
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

int precedence(char a)
{
    if(a == '*' || a == '/')
    {
        return 3;
    }
    else if(a == ' ' || a == '-')
    {
        return 2;
    }
    else
    {
        return -1;
    }
}

char* infix_postfix(char *infix)
{
    struct stack *sp = (struct stack *) malloc(sizeof(struct stack));

    sp->size = 100;
    sp->top = -1;
    sp->arr = (char *) malloc(sp->size * sizeof(char));
    char *postfix = (char *) malloc((strlen(infix 1)) * sizeof(char));

    int i=0; 
    int j=0;
    
    while(infix[i] != '\0')
    {
        if(infix[i] == '(')
        {
            push(sp,infix[i]);
            i  ;
        }
        else if(infix[i] == ')')
        {
            while(!(isEmpty(sp)) && stackTop(sp) != '(')
            {
                postfix[j] = pop(sp);
                j  ;
            }
      
            pop(sp);
               
        }
        else if(!isOperator(infix[i]))
        {
            postfix[j] = infix[i];
            i  ;
            j  ;
        }
        else
        {
            while(!(isEmpty(sp)) && precedence(infix[i])<=precedence(stackTop(sp)))
            {
                postfix[j] = pop(sp);
                j  ;
                
            }
            
            push(sp,infix[i]);
            i  ;
            
        }
    }
    while(!isEmpty(sp))
    {
        postfix[j] = pop(sp);
        j  ;
    }

    postfix[j] = '\0';
    return postfix;
}

int main(void)
{
    char *infix = "(x-y/z-k*d)";

    printf("postfix is %s",infix_postfix(infix));

    return 0;
}

CodePudding user response：

Code stuck on ')'.

Adding a i ; somewhere in the else if(infix[i] == ')') { .... } block resulted in below. Else code continues to parse ')'.

postfix is xyz/-kd*-

How bug was found:

Added a debug print.

while (infix[i] != '\0') {
  printf("Infix: %d %c\n", infix[i], infix[i]);  // added

That led to see code stuck when ')' was parsed.