#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;
}
此代码执行 RPN(逆波兰表示法)转换,但在 1 个块中给出明确的丢失。 根据 valgrind 的说法,代码存在内存泄漏问题。该消息很神秘,但我猜它是在 realloc() 中。 也许对消息有帮助:
输入数学表达式:5+9+21 转速:59+21+
无效的 free()/delete/delete[]/realloc() 在 0x484810F:免费 通过 0x1092FE:主要(exer1_2.c:34) 地址 0x4a78040 是大小为 1 的块内的 0 字节已释放 在 0x484ABC0:重新分配 通过 0x109616:推送(exer1_2.c:92) 通过 0x1094BB:转换为RPN 通过 0x1092D4:主要 块分配于 在 0x4845828:malloc 通过 0x109256:主要
堆摘要: 退出时使用:1 个块中 2 个字节 堆总使用量:4 次分配、4 次释放、已分配 2,051 字节
泄漏摘要: 肯定丢失:1 个块中 2 个字节 间接丢失:0 个块中的 0 个字节 可能丢失:0 个块中的 0 个字节 仍然可达:0 个块中的 0 个字节 抑制:0 个块中的 0 个字节
错误摘要:来自 1 个上下文的 1 个错误(已抑制:来自 0 的 0 个错误)
总的来说,我猜问题出在我的堆栈实现上。
程序中有一个错误。指针
stack
通过值传递给函数
convertToRPN
void convertToRPN(char*, char*, char*);
//...
convertToRPN(expression, stack, rpn);
因此该函数处理原始指针值的副本。原来的指针保持不变。因此,指针具有无效值,并且在
free
中调用
main
free(stack);
不释放函数执行期间分配的内存
convertToRPN
。
您至少应该通过指向函数的指针来传递对函数的引用。