reversed string not being returned in a c function in program of infix to prefix

Question

Below is the code for infix to prefix conversion. My code works fine until the use of reverse function where it does not print any string after copying. I have tried using a for loop to copy the reversed string but the outcome remains the same and the program terminates without giving proper output. Print statements in the reverse function work before copying but not after that. Could anyone let me know where the problem is?

#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 * reverse(char exp[])
{
    int l = strlen(exp);
    int j = 0;
    char temp[l];

    for(int i=l-1;i>=0;i--,j++)
    {
        temp[j] = exp[i];
    } 
    
    
    
    temp[j] = '\0';
    printf("prefix is %s",temp);
    
    strcpy(exp,temp);
    // for(int i=0;i<=l;i++)
    // {
    //     exp[i] = temp[i];
    // }
    printf("prefix is %s",exp);
    return exp;
}

char * infix_prefix(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 *prefix = (char *) malloc((strlen(infix+1)) * sizeof(char));

    
    infix = reverse(infix);
    

    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) != ')')
            {
                prefix[j] = pop(sp);
                j++;
            }
            if(!isEmpty(sp))
            {
                pop(sp);
                i++;      
            } 
            else
            { 
                printf("Incorrect Expression");
                exit(0); 
            }
        }
        else if(!isOperator(infix[i]))
        {
            prefix[j] = infix[i];
            i++;
            j++;
        }
        else if(isOperator(infix[i]))
        {
            while(!isEmpty(sp) && precedence(infix[i])<=precedence(stackTop(sp)))
            {
                prefix[j] = pop(sp);
                j++; 
            }     
            push(sp,infix[i]);
            i++;   
        }
        else
        {
            printf("Incorrect expression");
            exit(0);
        }
    }

    while(!isEmpty(sp) && stackTop(sp) != '(')
    {
        prefix[j] = pop(sp);
        j++;
    }

    if(stackTop(sp) == ')')
    {
        printf("Incorrect expression");
        exit(0);
    }

    
    prefix = reverse(prefix);
    
    prefix[j] = '\0';
    
    return prefix;
}

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

    printf("prefix is %s",infix_prefix(infix));

    return 0;
}

Answer 1

The reverse indeed has a problem: the temp array is defined with a length of l: that's not long enough to store the null terminator at temp[j] after the loop, causing undefined behavior.

There are more problems:

• char *prefix = (char *) malloc((strlen(infix+1)) * sizeof(char)); does not allocate enough space for a copy of infix. You should write char *prefix = malloc(strlen(infix) + 1);

• infix = reverse(infix); will crash because the argument to infix_prefix is a string literal which must not be modified. You should declare the argument as const char *infix and make a modifiable copy with strdup() if reversing is really needed, which I doubt very much.

Here is a modified version of reverse that performs the reverse operation in place:

char *reverse(char exp[]) {
    int i = 0;
    int j = strlen(exp);

    while (j-- > i) {
        char c = exp[j];
        exp[j] = exp[i];
        exp[i++] = c;
    }
    return exp;
}