印刷抽象语法树，无限递归问题(Printing Abstract Syntax Tree, infi

对于我的C编程类项目的最后，我们正在实施一个逆波兰式计算器，它可以评估的正确性表达式，返回相应的中缀表达式，或者打印出模拟的汇编代码。要做到这一点，我们要同时实现堆栈和抽象语法树。

struct snode /*stack data structure */
{
  int datum;
  struct snode* bottom;
};

struct tnode /*tree data structure */
{
  int datum;
  struct tnode* left;
  struct tnode* right;
};

目前，我设计我的程序从标准输入读取，并把元素到栈上，然后使用该堆栈来创建一个抽象语法树以后可以用来评估表达。对于现在，我还没有把任何检查呢，我只是想先建立一个AST。

下面是我的大部分主要功能。对于现在，有没有检查，以确保给定的公式是正确的。

int i = 1;


struct snode *stack;
stack = push(stack, -999); /* Here I set what will be the "empty" value of my stack. There's better ways to do it, but this is how I did it for a previous lab and it tended to cause less issues for me when I check if my stack is empty at the end */

struct tnode *AST;
AST = (struct tnode*)malloc(sizeof(struct tnode));
AST->datum = -7062; /*same thing as with stack, this is just a place holder that will be over written. */
AST->right = NULL;
AST -> left = NULL;

struct tnode* tmp;
tmp = (struct tnode*)malloc(sizeof(struct tnode));
tmp -> datum = -7062;
tmp -> right = NULL;
tmp -> left = NULL;

/*Operators are given as letters instead of +,-, etc. */
char *addition = "A"
char *subtraction = "S";
char *multiplication = "X";
char *division = "D"
char *mod = "M";

while(argv[i] !=NULL){
    if(isdigit(unsignedchar)argv[i][0])){
      stack = push(stack, atol(argv[i]));
   }else{ /* In the final code, a strcmp will check to see if argv[i] is one of the above A,S,X,D, or M arguments. For right now, it just fires if it's not a digit for my testing. */
       if(AST->datum == -7062){ /*if this is the first time we're running it*/
         AST->datum = atol(argv[i]);
         AST->right = create_node(stack->datum);
         stack = pop(stack);
         AST -> left = create_node(stack->datum);
         stack = pop(stack); /* I pop the top off the stack twice to get the 2 integers it stores. I know it will for the current testing, checks will be in place later */
       }else{ /* if AST already has elements in it. */
         tmp = AST;
         tmp -> left = tmp-> right = NULL;
         AST->datum = atol(argv[i]);
         AST->right = create_node(stack->datum);
         stack = pop(stack);
         AST->left = tmp; /*This puts the new operator as the root of the tree, the old tree as the left child of that root, and the right child as the integer stored on stack.*/
         }
     }
  i++;
  }

print_table(AST); /*Should print the AST */
}

create_node分配空间和存储什么给了它。

struct tnode*
create_node(int x){
  struct tnode* tmp;
  tmp = (struct tnode*)malloc(sizeof(struct tnode))
  tmp->datum = x;
  tmp->right = NULL;
  tmp->left = NULL;
  return tmp;
}

PRINT_TABLE递归打印抽象语法树。

void
print_table(struct tnode *AST){
    if(AST !=NULL){
        print_table(AST->left);
        printf("%d ", AST->datum);
        print_table(AST->right);
      }
  }

现在目前，如果下面给出：/ rpcalc 5 4 A，则该程序将返回5 0 4，我明白为什么一个正在恢复为0，所以这部分工作如预期。然而，当我尝试，得到程序/ rpcalc 5 4 A 3 X，其为（5 + 4）* 3，冻结了一会儿，然后返回一个段错误。

使用多个printf语句，我已经分离的问题倒在PRINT_TABLE函数的递归。出于某种原因，AST->左不似乎到达NULL指针终止程序，使其无限运行，直到程序崩溃。我不知道是什么导致了这一点，不幸的是，直到我解决这个问题我真的不能继续用任何我的项目远..

Answer 1:

让我们开始就在中间：

       }else{ /* if AST already has elements in it. */
         tmp = AST;
         tmp -> left = tmp-> right = NULL;
         AST->datum = atol(argv[i]);
         AST->right = create_node(stack->datum);
         stack = pop(stack);
         AST->left = tmp; /*This puts the new operator as the root of the tree, the old tree as the left child of that root, and the right child as the integer stored on stack.*/
         }
     }
  i++;
  }

这不好。您可以设置tmp = AST ，然后tmp->left和tmp->right以NULL ，但也设置AST->left和AST->right以NULL ，因为它们指向同一个东西！后来，你设置AST->left = tmp ，它创建了一个循环，因为再次， AST和tmp指向同一个东西，所以它相当于AST->left = AST 。递归到AST->left因此是无限的后裔，AKA 堆栈溢出 。

Answer 2:

虽然你的代码的无限递归的原因已经被EOF的答案给出，考虑看看代码我忍不住告诉你，至少我看来，也许你应该重新考虑你的算法了。

最有可能它是不是数字（ int你想保持在堆栈上），但AST片段。想像这样的表达式1 2 + 3 4 + *或更深嵌套的。改变struct snode到：

struct snode /*stack data structure */
{
    struct tnode* datum; /* we want to store AST nodes here !! */
    struct snode* bottom;
};

您的代码可能看起来像：

int main(int argc, char* argv[]) {
    int i = 1;

    struct snode *stack = NULL;
    struct tnode *AST = NULL;

    while(argv[i] !=NULL){

        /* isdigit takes argument of type char! don't typecast here */
        if(isdigit(argv[i][0])){ 
            stack = push(stack, create_node(atol(argv[i])));
        } 
        else {
            /* original code using atol(argv[i]), always returning 0 here */
            AST = create_node(0); 
            AST->left = stack->datum;
            stack = pop(stack);
            AST->right = stack->datum;
            stack = pop (stack);
            stack = push(stack, AST);
        }
        i++;
    }

    if (stack != NULL) {
        AST = stack->datum;
        print_table(AST); /*Should print the AST */
    }

    return 0;
}

输入5 4 A 3 X将产生3 0 4 0 5如预期，所以应该还有足够你在工作。

在这一使命的好运气。

可以肯定，我们在这里谈论同样的事实。对于push()和pop() ，而不是在你的代码片段给出，我用下面的代码。

struct snode* push(struct snode* stack, struct tnode* datum) {
    struct snode *S = (struct snode*)malloc(sizeof(struct snode));
    S->datum = datum;
    S->bottom = stack;
    return S;
}

struct snode* pop(struct snode* stack) {
    struct snode *S;
    if (stack == NULL)
        return NULL;
    S = stack->bottom;
    free(stack);
    return S;
}

文章来源: Printing Abstract Syntax Tree, infinite recursion issue