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

Question

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

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 分配空间并存储提供给它的内容。

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。我明白为什么 A 返回 0，所以这部分按预期工作。但是，当我尝试给程序/rpcalc 5 4 A 3 X，即 (5+4)*3 时，它会卡住片刻，然后返回一个 Segmentation Fault。

使用多个 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，但是 < em>还 将AST->left 和AST->right 设置为NULL，因为它们指向同一事物!稍后，您设置 AST->left = tmp，这会创建一个循环，因为 AST 和 tmp 再次指向同一事物，所以它等同于 AST->left = AST。因此，递归到 AST->left 是无限下降，也就是 堆栈溢出。