打印抽象语法树，无限递归问题

Question

对于我的 C 编程的最终项目 class，我们正在实现一个逆波兰符号计算器，它可以评估表达式的正确性，return 相应的中缀表达式，或者打印出模拟汇编代码。为此，我们将同时实现堆栈和抽象语法树。

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

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

目前，我将我的程序设计为从 stdin 读取并将元素放入堆栈，然后使用该堆栈创建抽象语法树，稍后可用于计算表达式。目前，我还没有进行任何检查，我只是想先构建一个 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 分配 space 并存储提供给它的内容。

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 然后程序将 return 5 0 4。我理解为什么 A returning 为 0，所以这部分按预期工作。但是，当我尝试给程序 /rpcalc 5 4 A 3 X，即 (5+4)*3 时，它冻结了片刻，然后 return 出现了分段错误。

使用几个 printf 语句，我将问题归结为 print_table 函数中的递归。由于某种原因，AST->left 似乎没有到达 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 是无限下降，又名 堆栈溢出.

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

c

recursion

stack

abstract-syntax-tree