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が渡されていると思いますか?

答え:同じ値です。1 つが (シーケンス ポイントの問題であるため、どちらかはわかりません)、もう 1 つの呼び出しは、同じ (解放された) ノードで同じスタック ポインターを取得し、人生は素晴らしいと考えながら楽しく実行されます。実際には、未定義の動作の道をたどろうとしています。

スタックは、スタック管理関数の他の場所にあるのと同じように、アドレスによって に渡される必要があり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 ランスルーsscanf(data, "%d", &integer)は喜んで吸い出し123ますが、これはあなたが望んでいたものではありません。

于 2013-11-11T07:01:48.463 に答える