c - 在C中使用递归调用时遇到问题

Question

我正在开发一个项目，需要我构建一个表达式堆栈(+、-、/、*、%、变量名)，并从该堆栈中在父级中以二进制形式构建一个表达式树，对吧，留下订单。我之前用 Python 做过这个项目，使用递归来完成这个任务相当简单，但 C 似乎不想配合。我想递归地执行此操作的原因是因为就像我说的，我以前做过，并且这是我知道的唯一方法。我认为问题出在递归调用中，因为没有打印任何打印函数。我希望我已经提供了足够的信息让你们了解我正在尝试做什么以及我面临的问题，谢谢!

//this builds our stack of expression tokens
ExpNode* buildStack (char expr[]){
   StackNode *stack;
   char *pch;
   int counter = 0;
   pch = strtok(expr, " ");

   //build the stack of tokens
   while (pch != NULL){
      //initialize the stack with the first token
      if (counter == 0){
         stack = makeStackNode(pch, NULL);
         counter = 1;
       }
       pch = strtok(NULL, " " );
       //out of tokens, break out of the loop
       if (pch == NULL){
          break;
       }
       //push the next token onto the stack
       push(&stack, pch);
   }

   ExpNode *node;
   printf("about to build tree\n");
   node = buildExpTreeRec(stack);
   if (node == NULL){
      printf("ITS A NULL");
   }
   else{
      printf("ITS NOT A NULL"); // this line doesn't get printed but it should
   }

   printf("returning the node\n"); // this line doesn't get printed but it should
   return node;
}

//this builds our binary expression tree
ExpNode *buildExpTreeRec(StackNode *stack){
   printf("top of the stack is %s \n", top(stack));
   if (emptyStack(stack) != 0){
      printf("HOUSTON WE HAVE A PROBLEM");
   }
   else{
      char *data = top(stack);
      pop(&stack);
      ExpNode *node;
      printf("Right before we makeExpNode\n");

      //I believe the issue is here
      node = makeExpNode(data, buildExpTreeRec(stack), buildExpTreeRec(stack));
      printf("Right after we makeExpNode\n"); // this line doesn't get printed but it should
      return node;
   }
   printf("About to return a NULL\n");
   return NULL;
}

//this builds our expression node
ExpNode* makeExpNode(char token[], ExpNode* left, ExpNode* right){
   printf("token is : %s\n", token); //this line is never printed but it should
   char * pch;
   int integer;
   pch = strchr(token, '.');
   ExpNode *node = malloc(sizeof(ExpNode));

   //do stuff to make node
   //this function was tested and it works correctly without using recursive calls
   return node;
}

输出:

列表项

a b + // this is user input
Made stack node with a
Made stack node with b
Pushed b onto the stack
Made stack node with +

Pushed + onto the stack
about to build tree
top of the stack is +

Right before we makeExpNode
top of the stack is b
Right before we makeExpNode
top of the stack is a
Right before we makeExpNode

问题出在递归函数调用作为参数的行中:

node = makeExpNode(data, buildExpTreeRec(stack), buildExpTreeRec(stack));

如果我将行更改为:

 node = makeExpNode(data, NULL, NULL);

我得到了正确的输出:

a //input
Made stack node with a
about to build tree
top of the stack is a
Right before we makeExpNode
token is : a
Done making EXPNODE
Right after we makeExpNode
ITS NOT A NULL

Answer 1

一位 friend 向我指出了这个问题，我的递归方法没有基本情况。

修复:

ExpNode *buildExpTreeRec(StackNode *stack){
    ExpNode *node;
    char *data = top(stack);
    pop(&stack);
    if (emptyStack(stack) != 0 ){
        node = makeExpNode(data, NULL, NULL); // needed this
    }
    else{
        printf("Right before we makeExpNode\n");
        node = makeExpNode(data,buildExpTreeRec(stack), buildExpTreeRec(stack));
        printf("Right after we makeExpNode\n");
    }
    return node;
}