cdata-structuresstackdynamic-memory-allocationrealloc

c stack (using dynamic array) realloc memory leak problem


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

int LENGTH = 1;
int TOP = -1;

void push(char**, char);
char pop(char*);
char peek(char*);
int isEmpty();
int isFull();

void convertToRPN(char*, char*, char*);
int isOperator(char);
int getPrecedence(char);


int main(void) {
    char* stack = (char*) malloc(sizeof(char) * LENGTH);
    if (!stack) {
        printf("Memory allocation failed./n");
        exit(1);
    }

    char expression[100];
    printf("Enter the mathematical expression: ");
    scanf("%s", expression);

    char rpn[100];
    convertToRPN(expression, stack, rpn);

    printf("The rpn: %s\n", rpn);

    free(stack);

    return 0;
}


int isOperator(char c) {
    return (c == '+' || c == '-' || c == '*' || c == '/');
}


int getPrecedence(char c) {
    if (c == '+' || c == '-')
        return 1;
    if (c == '*' || c == '/')
        return 2;
    return 0; 
}


void convertToRPN(char *expression, char* stack, char* rpn) {
    
    int j = 0;
    for (int i = 0; expression[i] != '\0'; i++) {
        if (expression[i] >= '0' && expression[i] <= '9') {
            rpn[j] = expression[i];
            j++;
        } else if (isOperator(expression[i])) {
            while (!isEmpty() && peek(stack) != '(' && getPrecedence(peek(stack)) >= getPrecedence(expression[i])) {
                rpn[j] = pop(stack);
                j++;
            }
            push(&stack, expression[i]);
        } else if (expression[i] == '(') {
            push(&stack, expression[i]);
        } else if (expression[i] == ')') {
            while (!isEmpty() && peek(stack) != '(') {
                rpn[j] = pop(stack);
                j++;
            }
            pop(stack);
        } else {
            printf("Unsupported character.\n");
            exit(2);
        }
    }

    while (!isEmpty()) {
        rpn[j] = pop(stack);
        j++;
    }

    rpn[j] = '\0';
}


void push(char **stack, char c) {
    if (isFull()) {
        *stack = (char *)realloc(*stack, sizeof(char) * (LENGTH + 1));
        if (!*stack) {
            printf("Memory reallocation failed.\n");
            exit(5);
        }
        LENGTH++;
    }
    TOP++;
    (*stack)[TOP] = c;
}


char pop(char *stack) {
    if (isEmpty()) {
        printf("POP: the stack is empty.\n");
        exit(3);
    } else {
        char item = stack[TOP];
        TOP--;
        return item;
    }
}


char peek(char *stack) {
    if (isEmpty()) {
        printf("PEEK: the stack is empty.\n");
        exit(4);
    }
    return stack[TOP];
}


int isEmpty() {
    return TOP == -1;
}


int isFull() {
    return TOP == LENGTH - 1;
}

This code performs RPN (Reverse Polish notation) conversion, but gives definite lost in 1 block. According to valgrind the code has a memory leak issue.The message is cryptic, but I guess it's in realloc(). Maybe to help the message:

Enter the mathematical expression: 5+9+21 The rpn: 59+21+

Invalid free() / delete / delete[] / realloc() at 0x484810F: free by 0x1092FE: main (exer1_2.c:34) Address 0x4a78040 is 0 bytes inside a block of size 1 free'd at 0x484ABC0: realloc by 0x109616: push (exer1_2.c:92) by 0x1094BB: convertToRPN by 0x1092D4: main Block was alloc'd at at 0x4845828: malloc by 0x109256: main

HEAP SUMMARY: in use at exit: 2 bytes in 1 blocks total heap usage: 4 allocs, 4 frees, 2,051 bytes allocated

LEAK SUMMARY: definitely lost: 2 bytes in 1 blocks indirectly lost: 0 bytes in 0 blocks possibly lost: 0 bytes in 0 blocks still reachable: 0 bytes in 0 blocks suppressed: 0 bytes in 0 blocks

ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

Overall i guess the problem is about my implementation of the stack.


Solution

  • There is a bug in the program. The pointer stack is passed to the function convertToRPN by value

    void convertToRPN(char*, char*, char*);
    
    //...
    
    convertToRPN(expression, stack, rpn);
    

    So the function deals with a copy of the value of the original pointer. The original pointer stays unchanged. As a result the pointer has an invalid value and this call of free in main

    free(stack);
    

    does not free the memory allocated during execution of the function convertToRPN.

    You should at least pass the pointer by reference to the function through a pointer to it. That is the function should be declared and called like

    void convertToRPN(char*, char**, char*);
    
    //...
    
    convertToRPN(expression, &stack, rpn);
    

    though it would be better if neither memory for the stack was allocated in main. The stack is used in the function convertToRPN where memory should be allocated and freed.

    And it would be better to declare a structure Stack like for example

    struct Stack
    {
        size_t top;
        size_t size;  
        char *mem;
    };
    

    and use an object of the structure instead of several separate variables. And it is a very bad idea to use global variables

    int LENGTH = 1;
    int TOP = -1;
    

    I advise you to redesign the code.