Double free or corruption error with Stack and Bin

Question

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 detected ./interp: double free or corruption (fasttop): 0x0934d018 **

Here is my 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

Here are my stack functions

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;
   }
}

Output from prints:

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

Answer 1

Your problem is this:

return makeTreeNode(data, buildTree(stack), buildTree(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.

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);
}

Output

parser: operator node
parser: variable node
parser: variable node

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.