Je reçois l’erreur suivante lorsque j’essaie de créer un arbre d’expression binary à partir d’une stack. Je crois que le problème est celui où je saute dans la fonction récursive, je pense que je saute sur une stack vide mais je ne connais pas la solution.
* glibc détectée ./interp: double libre ou corruption (fasttop): 0x0934d018 * *
Voici mon code:
//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
Voici mes fonctions de stack
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; } }
Sortie des impressions:
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
Votre problème est le suivant:
return makeTreeNode(data, buildTree(stack), buildTree(stack));
stack
vous, quelle valeur de stack
est transmise à chacune de ces invocations de fonctions?
Réponse: la même valeur. Quand on (on ne sait pas, peu importe, puisqu’il s’agit d’un problème de sharepoint séquence), l’autre invoke prend le même pointeur de stack au même nœud (maintenant libéré) et court joyeusement en pensant que la vie est belle, quand en réalité, il est sur le sharepoint conduire sur la voie d’un comportement indéfini.
Votre stack doit être passée par adresse à buildTree()
, exactement comme à d’autres endroits dans vos fonctions de gestion de stack (car c’est exactement ce que buildTree()
fait: gérer la stack d’entrée).
Enfin, une fois que vous avez résolu le problème, vous devez résoudre le problème de cet appel de fonction, mais je vous le laisse. (Pas vraiment, voir ci-dessous)
//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); }
Sortie
parser: operator node parser: variable node parser: variable node
Note latérale: J’ai effectué un nettoyage sur buildTree()
, y compris l’inversion que vous recherchez en premier: une décimale ou un entier. 123.456 dans sscanf(data, "%d", &integer)
heureusement 123
, et ce n’est pas ce que vous vouliez par son apparence.