1

尝试从堆栈构建二进制表达式树时出现以下错误。我相信问题是我在递归函数中弹出，我想我在一个空堆栈上弹出，但我不知道解决方案。

* 检测到 glibc./interp：双重释放或损坏（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
4

1 回答 1

3

你的问题是这样的：

return makeTreeNode(data, buildTree(stack), buildTree(stack));

stack您认为传递给每个函数调用的价值是什么？

答：相同的值。当一个（我们不知道，不关心哪个，因为这是一个序列点问题），另一个调用在同一个（现在被释放的）节点上获取相同的堆栈指针，并愉快地运行，认为生活很美好，当实际上，它即将走上未定义行为的道路。

您的堆栈需要按地址传递给buildTree()，就像在堆栈管理函数中的其他位置一样（因为这正是buildTree()正在做的事情：管理输入堆栈）。

最后，一旦你解决了这个问题，你就需要解决该函数调用的序列点问题，但我留给你。（不是真的，见下文）

//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()，包括反转您首先检查的内容：小数或整数。123.456 run throughsscanf(data, "%d", &integer)会很高兴地吸123出来，这不是你想要的。

于 2013-11-11T07:01:48.463 回答