0

我正在做一个项目，该项目需要我构建一堆表达式（+、-、/、*、%、变量名），并从该堆栈中以父、右、左顺序构建一个二进制形式的表达式树。我以前在 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
4

1 回答 1

0

一位朋友向我指出了这个问题，我的递归方法没有基本案例。

使固定：

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;
}
于 2013-11-10T01:50:12.010 回答