堆栈和二进制表达式树出现双重释放或损坏错误 [英] Double free or corruption error with Stack and Binary Expression Tree
问题描述
尝试从堆栈构建二进制表达式树时，出现以下错误.我认为问题在于我正在递归函数中弹出，我认为我正在空栈中弹出，但是我不知道解决方案.
I am getting the following error when trying to build a binary expression tree from a Stack. I believe the issue is where I am popping in the recursive function, I think I am popping on an empty stack but I don't know the solution.
* glibc检测到 ./interp:双重释放或损坏(快速更新):0x0934d018 * *
* glibc detected ./interp: double free or corruption (fasttop): 0x0934d018 **
这是我的代码:
//This is the main
int main(int argc, char *argv[]){
TreeNode *node;
StackNode *stack = NULL;
push(&stack, "a");
push(&stack, "b");
push(&stack, "+");
//while (emptyStack(stack)!= 1){ //this while loop works correctly, which verifies that my stack implementation is working.
// printf("Top is : %s\n", top(stack));
// pop(&stack);
//}
node = buildTree(stack);
//buildTree function
TreeNode *buildTree(StackNode *stack){
int integer; //to check for an integer
char *data = top(stack);
char *pch = strchr(top(stack), '.'); //to check for a double, looks for the decimal point
if (emptyStack(stack) != 0){
//stack is empty
fprintf(stderr, "Invalid expression, not enough tokens");
return NULL;
}
else if (sscanf(top(stack), "%d", &integer) != 0){
printf("parser: integer node\n");
//got an integer
pop(&stack);
return makeTreeNode(data, NULL, NULL);
}
else if (pch != NULL){
printf("parser: double node\n");
//got a double
pop(&stack);
return makeTreeNode(data, NULL, NULL);
}
else if ( isalpha((int)data[0])){
//got a variable
printf("parser: variable node\n");
pop(&stack);
return makeTreeNode(data, NULL, NULL);
}
else{
//got an operator, recurse
printf("parser: operator node\n");
pop(&stack);
return makeTreeNode(data,buildTree(stack), buildTree(stack));
}
}
//makeTreeNode
TreeNode* makeTreeNode(char token[], TreeNode* left, TreeNode* right){
//this function works correctly
这是我的堆栈函数
StackNode* makeStackNode(char* data, StackNode* next){
StackNode *node;
node = malloc(sizeof(StackNode));
node->data = data;
node->next = next;
printf("Making stack node of : %s\n", data);
return node;
}
char* top(StackNode* stack){
if (emptyStack(stack)!= 0){
exit(EXIT_FAILURE);
}
else{
return stack->data;
}
}
void push(StackNode** stack, char* data){
StackNode* ptr;
ptr = makeStackNode(data, *stack);
*stack = ptr;
printf("Pushed stack node \n");
}
//pop from stack
void pop (StackNode** stack){
if (emptyStack(*stack)!=0){
exit(EXIT_FAILURE);
}
else{
printf("Popping node \n");
StackNode* ptr = *stack;
printf("Right before the pop, stack = %s\n", top(*stack));
*stack = ptr->next;
printf("Right before the free, stack = %s\n", top(*stack));
free(ptr);
}
}
//returns 1 if stack is empty, 0 if it is not empty
int emptyStack(StackNode* stack){
if (stack == NULL){
return 1;
}
else{
return 0;
}
}
打印输出:
Making stack node of : a
Pushed stack node
Making stack node of : b
Pushed stack node
Making stack node of : +
Pushed stack node
parser: operator node
Popping node
Right before the pop, stack = +
Right before the free, stack = b
parser: variable node
Popping node
Right before the pop, stack = b
Right before the free, stack = a
parser: integer node //this should be a variable node
Popping node
Right before the pop, stack = //this should be stack = a
Right before the free, stack = a //this should be blank
推荐答案
您的问题是这样的:
return makeTreeNode(data, buildTree(stack), buildTree(stack));
您认为将stack的值传递给每个这些函数调用吗?
What value for stack do you think is being passed to each of those functions invocations?
答案:相同值.当一个(我们不知道，不关心哪个，因为那是一个序列点问题)时，另一个调用在相同(现已释放)的节点上使用相同的堆栈指针，并在认为生命很好时快乐地运行，当实际上，它正沿着未定义行为的道路前进.
Answer: The same value. When one (we don't know, no care which, as that is a sequence point issue), The other invoke takes the same stack pointer at the same (now-freed) node, and runs happily along thinking life is great, when in reality, its about to drive down the road of undefined behavior.
您的堆栈需要按地址传递给buildTree()，就像它在堆栈管理功能中的其他位置一样(因为这正是buildTree()所做的:管理输入堆栈).
Your stack needs to be passed by-address to buildTree(), just as it is in the other places in your stack management functions (because that is exactly what buildTree() is doing: managing the input stack).
最后，修复此问题之后，您需要修复该函数调用的顺序点问题，但是我要留给您. (不是，请参见下文)
Finally once you fix that, you then need to fix the sequence-point issue of that function call, but that I leave to you. (Not really, see below)
//buildTree function
TreeNode *buildTree(StackNode **stack)
{
char *data=NULL;
int integer;
if (stack == NULL)
{
//stack is empty
fprintf(stderr, "Invalid expression, not enough tokens");
return NULL;
}
// reference top of stack data
data = top(*stack);
if (strchr(data,'.') != NULL)
{
printf("parser: double node\n");
pop(stack);
return makeTreeNode(data, NULL, NULL);
}
if (sscanf(data, "%d", &integer) != 0)
{
printf("parser: integer node\n");
pop(stack);
return makeTreeNode(data, NULL, NULL);
}
if ( isalpha((int)data[0]))
{
printf("parser: variable node\n");
pop(stack);
return makeTreeNode(data, NULL, NULL);
}
//got an operator, recurse
printf("parser: operator node\n");
pop(stack);
TreeNode *rhs = buildTree(stack);
TreeNode *lhs = buildTree(stack);
return makeTreeNode(data, lhs, rhs);
}
//This is the main
int main(int argc, char *argv[])
{
TreeNode *node;
StackNode *stack = NULL;
push(&stack, "a");
push(&stack, "b");
push(&stack, "+");
node = buildTree(&stack);
}
输出
parser: operator node
parser: variable node
parser: variable node
侧面注意:我对buildTree()进行了一些清理，包括反转您首先检查的内容:十进制或整数.通过sscanf(data, "%d", &integer)运行123.456会很高兴将123吸出，而这并不是您所希望的.
Side Note: I did some cleanup on buildTree(), including reversing which you check for first: a decimal or an integer. 123.456 run through sscanf(data, "%d", &integer) will happily suck 123 out, and that isn't what you wanted by the looks of this.
这篇关于堆栈和二进制表达式树出现双重释放或损坏错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
