基于动态数组的C栈realloc内存泄漏问题排查求助

问题背景 #

这段C语言代码通过动态数组实现栈，完成中缀表达式到逆波兰表达式（RPN）的转换，但经Valgrind检测存在两个内存问题：

• 1块2字节内存确定丢失
• 触发Invalid free()报错
  推测问题出在栈的realloc实现部分，以下是完整代码、测试情况及Valgrind检测日志。

原代码 #

#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;
}

测试情况 #

• 输入：5+9+2*1
• 输出RPN：59+21*+

Valgrind检测日志 #

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

堆内存摘要：
in use at exit: 2 bytes in 1 blocks
total heap usage: 4 allocs, 4 frees, 2,051 bytes allocated

泄漏摘要：
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

错误摘要：1 errors from 1 contexts (suppressed: 0 from 0)

问题分析与修复方案 #

核心问题 #

1. Invalid free()原因：
   convertToRPN函数接收的stack是值传递，调用push(&stack, ...)时，push内部通过realloc修改的栈内存地址仅在convertToRPN的局部变量中生效，main函数里的stack指针仍指向最初malloc的旧地址。而realloc扩容时已自动释放旧内存块，最终main中free(stack)是在释放一个已被回收的地址，触发Invalid free()错误。

2. 内存泄漏原因：
   realloc分配的新内存地址仅保存在convertToRPN的局部stack变量中，main无法持有该地址，程序退出时未释放这块新内存，导致内存泄漏。

修复步骤 #

1. 修改convertToRPN的函数声明与定义，让它接收栈指针的指针，确保栈地址的修改能同步到main：

// 函数声明
void convertToRPN(char*, char**, char*);

// 函数定义
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';
}

2. 修改main中调用convertToRPN的代码：

convertToRPN(expression, &stack, rpn);

额外优化建议 #

• 移除全局变量LENGTH和TOP，将栈封装为结构体（包含栈指针、容量、栈顶索引），提升代码的线程安全性与可读性。
• 扩容时采用倍增策略（如每次扩容为原容量的2倍），减少realloc调用次数，提升性能。

内容的提问来源于stack exchange，提问作者Nurana