Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

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

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

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.

Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading