我在下面写了一个程序把中缀表达式转换成后缀表达式。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Stack{
int top;
int capacity;
char *array;
}Stack;
int isEmpty(Stack *s){
return s->top == -1;
}
char pop(Stack *s){
char c;
if(isEmpty(s))
return -1;
c = s->array[s->top];
s->array[s->top--] = '\0';
return c;
}
void push(Stack *s,char c){
s->array[++s->top] = c;
}
char peek(Stack *s){
return s->array[s->top];
}
char *toString(char c){
char *str = (char *)malloc(sizeof(char)*2);
str[0] = c;
str[1] = '\0';
return str;
}
int hasGreaterPriority(char c1,char c2){
if(c1 == '*' && (c2 == '+' || c2 == '-'))
return 1;
else if(c1 == '/' && (c2 == '+' || c2 == '-'))
return 1;
else
return 0;
}
void infixtopostfix(char exp[]){
int len = strlen(exp),i;
char *out = (char *)malloc(sizeof(char));
out[0] = '\0';
Stack *stack = (Stack *)malloc(sizeof(Stack));
stack->capacity = len;
stack->top = -1;
stack->array = malloc(sizeof(char)*len);
for(i=0; i<len; i++){
if(exp[i] >= 'a' && exp[i] <= 'z')
strcat(out,toString(exp[i]));
else if(exp[i] == ')'){
while(peek(stack) != '(')
strcat(out,toString(pop(stack)));
pop(stack);
}
else{
if(isEmpty(stack) || exp[i] == '(')
push(stack,exp[i]);
else if(hasGreaterPriority(peek(stack),exp[i])){
strcat(out,toString(pop(stack)));
push(stack,exp[i]);
}
else
push(stack,exp[i]);
}
}
/* UNTIL HERE */
while(!isEmpty(stack))
strcat(out,toString(pop(stack)));
printf("Postfix Expression: %s\n",out);
}
int main(void) {
char exp[] = "a+b*(c/d-e)/(f+g*h)-i\0";
printf("Infix Expression: %s\n",exp);
infixtopostfix(exp);
return 0;
}
问题如下：
在infixtopostfix方法中，before-while用“until-here”表示出来的变量值似乎是正确的。我在gdb的帮助下查过了。经过两次while循环的迭代后，in out变量的值看起来也不错在最后一次迭代中，即在向外添加+时，该值如下所示
abcd/e-fgh*+/i-*\377\377\377\377\025+
如何将
\377\377\377\377\025+添加到输出变量？预期值将
abcd/e-fgh*+/i-*+ 最佳答案
您已为空字符串分配了空间：
char *out = (char *)malloc(sizeof(char));
out[0] = '\0';
然后你会：
strcat(out,toString(exp[i]));
分配的空间不足，无法在
out结尾添加任何内容可能在某个地方有重新分配，但它很隐蔽。在风格上，你有：
if(exp[i] >= 'a' && exp[i] <= 'z')
strcat(out,toString(exp[i]));
else if(exp[i] == ')'){
while(peek(stack) != '(')
strcat(out,toString(pop(stack)));
pop(stack);
}
else{
if(isEmpty(stack) || exp[i] == '(')
push(stack,exp[i]);
else if(hasGreaterPriority(peek(stack),exp[i])){
strcat(out,toString(pop(stack)));
push(stack,exp[i]);
}
else
push(stack,exp[i]);
}
您可以避免一定程度的嵌套：
if(exp[i] >= 'a' && exp[i] <= 'z')
strcat(out,toString(exp[i]));
else if(exp[i] == ')'){
while(peek(stack) != '(')
strcat(out,toString(pop(stack)));
pop(stack);
}
else if(isEmpty(stack) || exp[i] == '(')
push(stack,exp[i]);
else if(hasGreaterPriority(peek(stack),exp[i])){
strcat(out,toString(pop(stack)));
push(stack,exp[i]);
}
else
push(stack,exp[i]);
这是自洽的；原始的不是。
瓦尔格林报告
我获取了您的代码，在每个函数之前添加了
static（主要是为了绕过我的默认编译选项），然后在main()下运行您的代码以获得输出：$ valgrind ./pfx-infix
==17722== Memcheck, a memory error detector
==17722== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==17722== Using Valgrind-3.9.0 and LibVEX; rerun with -h for copyright info
==17722== Command: ./pfx-infix
==17722==
Infix Expression: a+b*(c/d-e)/(f+g*h)-i
==17722== Invalid write of size 1
==17722== at 0x4C2BEF3: strcat (mc_replace_strmem.c:268)
==17722== by 0x4005D4: main (pfx-infix.c:67)
==17722== Address 0x51f2041 is 0 bytes after a block of size 1 alloc'd
==17722== at 0x4C2935F: malloc (vg_replace_malloc.c:291)
==17722== by 0x4004FF: main (pfx-infix.c:57)
==17722==
==17722== Invalid read of size 1
==17722== at 0x4C2BEC4: strcat (mc_replace_strmem.c:268)
==17722== by 0x4005D4: main (pfx-infix.c:67)
==17722== Address 0x51f2041 is 0 bytes after a block of size 1 alloc'd
==17722== at 0x4C2935F: malloc (vg_replace_malloc.c:291)
==17722== by 0x4004FF: main (pfx-infix.c:57)
==17722==
==17722== Invalid write of size 1
==17722== at 0x4C2BEE0: strcat (mc_replace_strmem.c:268)
==17722== by 0x4005D4: main (pfx-infix.c:67)
==17722== Address 0x51f2041 is 0 bytes after a block of size 1 alloc'd
==17722== at 0x4C2935F: malloc (vg_replace_malloc.c:291)
==17722== by 0x4004FF: main (pfx-infix.c:57)
==17722==
==17722== Invalid read of size 1
==17722== at 0x4C2BEC4: strcat (mc_replace_strmem.c:268)
==17722== by 0x400726: main (pfx-infix.c:77)
==17722== Address 0x51f2041 is 0 bytes after a block of size 1 alloc'd
==17722== at 0x4C2935F: malloc (vg_replace_malloc.c:291)
==17722== by 0x4004FF: main (pfx-infix.c:57)
==17722==
==17722== Invalid write of size 1
==17722== at 0x4C2BEE0: strcat (mc_replace_strmem.c:268)
==17722== by 0x400726: main (pfx-infix.c:77)
==17722== Address 0x51f2044 is 3 bytes after a block of size 1 alloc'd
==17722== at 0x4C2935F: malloc (vg_replace_malloc.c:291)
==17722== by 0x4004FF: main (pfx-infix.c:57)
==17722==
==17722== Invalid write of size 1
==17722== at 0x4C2BEF3: strcat (mc_replace_strmem.c:268)
==17722== by 0x400726: main (pfx-infix.c:77)
==17722== Address 0x51f2045 is 4 bytes after a block of size 1 alloc'd
==17722== at 0x4C2935F: malloc (vg_replace_malloc.c:291)
==17722== by 0x4004FF: main (pfx-infix.c:57)
==17722==
==17722== Invalid read of size 1
==17722== at 0x4C2BEC4: strcat (mc_replace_strmem.c:268)
==17722== by 0x4006A9: main (pfx-infix.c:70)
==17722== Address 0x51f2041 is 0 bytes after a block of size 1 alloc'd
==17722== at 0x4C2935F: malloc (vg_replace_malloc.c:291)
==17722== by 0x4004FF: main (pfx-infix.c:57)
==17722==
==17722== Invalid write of size 1
==17722== at 0x4C2BEE0: strcat (mc_replace_strmem.c:268)
==17722== by 0x4006A9: main (pfx-infix.c:70)
==17722== Address 0x51f2046 is 5 bytes after a block of size 1 alloc'd
==17722== at 0x4C2935F: malloc (vg_replace_malloc.c:291)
==17722== by 0x4004FF: main (pfx-infix.c:57)
==17722==
==17722== Invalid write of size 1
==17722== at 0x4C2BEF3: strcat (mc_replace_strmem.c:268)
==17722== by 0x4006A9: main (pfx-infix.c:70)
==17722== Address 0x51f2047 is 6 bytes after a block of size 1 alloc'd
==17722== at 0x4C2935F: malloc (vg_replace_malloc.c:291)
==17722== by 0x4004FF: main (pfx-infix.c:57)
==17722==
==17722== Invalid read of size 1
==17722== at 0x4C2BEC4: strcat (mc_replace_strmem.c:268)
==17722== by 0x40061E: main (pfx-infix.c:86)
==17722== Address 0x51f2041 is 0 bytes after a block of size 1 alloc'd
==17722== at 0x4C2935F: malloc (vg_replace_malloc.c:291)
==17722== by 0x4004FF: main (pfx-infix.c:57)
==17722==
==17722== Invalid write of size 1
==17722== at 0x4C2BEE0: strcat (mc_replace_strmem.c:268)
==17722== by 0x40061E: main (pfx-infix.c:86)
==17722== Address 0x51f204e is 13 bytes after a block of size 1 alloc'd
==17722== at 0x4C2935F: malloc (vg_replace_malloc.c:291)
==17722== by 0x4004FF: main (pfx-infix.c:57)
==17722==
==17722== Invalid write of size 1
==17722== at 0x4C2BEF3: strcat (mc_replace_strmem.c:268)
==17722== by 0x40061E: main (pfx-infix.c:86)
==17722== Address 0x51f204f is 14 bytes after a block of size 1 alloc'd
==17722== at 0x4C2935F: malloc (vg_replace_malloc.c:291)
==17722== by 0x4004FF: main (pfx-infix.c:57)
==17722==
==17722== Invalid read of size 1
==17722== at 0x4E7D3B1: vfprintf (vfprintf.c:1630)
==17722== by 0x4E858D8: printf (printf.c:35)
==17722== by 0x400633: main (pfx-infix.c:88)
==17722== Address 0x51f2041 is 0 bytes after a block of size 1 alloc'd
==17722== at 0x4C2935F: malloc (vg_replace_malloc.c:291)
==17722== by 0x4004FF: main (pfx-infix.c:57)
==17722==
==17722== Invalid read of size 1
==17722== at 0x4EAC184: _IO_file_xsputn@@GLIBC_2.2.5 (fileops.c:1330)
==17722== by 0x4E7CF81: vfprintf (vfprintf.c:1630)
==17722== by 0x4E858D8: printf (printf.c:35)
==17722== by 0x400633: main (pfx-infix.c:88)
==17722== Address 0x51f2050 is 15 bytes after a block of size 1 alloc'd
==17722== at 0x4C2935F: malloc (vg_replace_malloc.c:291)
==17722== by 0x4004FF: main (pfx-infix.c:57)
==17722==
==17722== Invalid read of size 1
==17722== at 0x4EAC199: _IO_file_xsputn@@GLIBC_2.2.5 (fileops.c:1330)
==17722== by 0x4E7CF81: vfprintf (vfprintf.c:1630)
==17722== by 0x4E858D8: printf (printf.c:35)
==17722== by 0x400633: main (pfx-infix.c:88)
==17722== Address 0x51f204f is 14 bytes after a block of size 1 alloc'd
==17722== at 0x4C2935F: malloc (vg_replace_malloc.c:291)
==17722== by 0x4004FF: main (pfx-infix.c:57)
==17722==
==17722== Invalid read of size 16
==17722== at 0x4EAC0DE: _IO_file_xsputn@@GLIBC_2.2.5 (fileops.c:1362)
==17722== by 0x4E7CF81: vfprintf (vfprintf.c:1630)
==17722== by 0x4E858D8: printf (printf.c:35)
==17722== by 0x400633: main (pfx-infix.c:88)
==17722== Address 0x51f2040 is 0 bytes inside a block of size 1 alloc'd
==17722== at 0x4C2935F: malloc (vg_replace_malloc.c:291)
==17722== by 0x4004FF: main (pfx-infix.c:57)
==17722==
==17722== Invalid read of size 1
==17722== at 0x4EAC100: _IO_file_xsputn@@GLIBC_2.2.5 (fileops.c:1362)
==17722== by 0x4E7CF81: vfprintf (vfprintf.c:1630)
==17722== by 0x4E858D8: printf (printf.c:35)
==17722== by 0x400633: main (pfx-infix.c:88)
==17722== Address 0x51f2050 is 15 bytes after a block of size 1 alloc'd
==17722== at 0x4C2935F: malloc (vg_replace_malloc.c:291)
==17722== by 0x4004FF: main (pfx-infix.c:57)
==17722==
Postfix Expression: abcd/e-fgh*+/i-*+
==17722==
==17722== HEAP SUMMARY:
==17722== in use at exit: 72 bytes in 20 blocks
==17722== total heap usage: 20 allocs, 0 frees, 72 bytes allocated
==17722==
==17722== LEAK SUMMARY:
==17722== definitely lost: 51 bytes in 19 blocks
==17722== indirectly lost: 21 bytes in 1 blocks
==17722== possibly lost: 0 bytes in 0 blocks
==17722== still reachable: 0 bytes in 0 blocks
==17722== suppressed: 0 bytes in 0 blocks
==17722== Rerun with --leak-check=full to see details of leaked memory
==17722==
==17722== For counts of detected and suppressed errors, rerun with: -v
==17722== ERROR SUMMARY: 204 errors from 17 contexts (suppressed: 2 from 2)
$
这清楚地标识了超出范围的内存访问；它也碰巧产生了“正确”的答案你也有一些内存泄漏应该被修复。