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

For the final project in my C programming class, we are implementing a reverse polish notation calculator which can either evaluate an expression for correctness, return the corresponding infix expression, or print out mock assembly code. To do so, we are to implement both a stack and a Abstract Syntax Tree.

对于我的C编程类中的最终项目,我们正在实现反向抛光表示法计算器,它可以评估表达式的正确性,返回相应的中缀表达式,或打印出模拟汇编代码。为此,我们要实现堆栈和抽象语法树。

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

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

Currently, I've designed my program to read from stdin and put the elements onto a stack, then to use that stack to create a Abstract Syntax Tree which can later be used to evaluate the expression. For right now, I haven't put in any checks yet, I'm just trying to build a AST first.

目前,我已经设计了我的程序来从stdin读取并将元素放到堆栈中,然后使用该堆栈创建一个抽象语法树,以后可以用它来评估表达式。现在,我还没有进行任何检查,我只是想先建立一个AST。

Below is the majority of my main function. For right now, there are no checks to ensure that the given equation is correct.

以下是我主要功能的大部分内容。目前,没有检查确保给定的方程是正确的。

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 allocates space and stores what's given to it.

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 recursively prints the Abstract Syntax Tree.

print_table以递归方式打印抽象语法树。

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

Now currently, if the following is given: /rpcalc 5 4 A Then the program will return 5 0 4. I understand why the A is returning as a 0, so this part is working as intended. However, when I try to give the program /rpcalc 5 4 A 3 X, which is (5+4)*3, it freezes for a moment and then returns a Segmentation Fault.

现在,如果给出以下内容:/ rpcalc 5 4 A然后程序将返回5 0 4.我理解为什么A返回0,所以这部分按预期工作。但是,当我尝试给程序/ rpcalc 5 4 A 3 X,即(5 + 4)* 3时,它会冻结片刻,然后返回分段错误。

Using several printf statements, I have isolated the issue down to the recursion in the print_table function. For some reason, the AST->left does not appear to be reaching the NULL pointer to terminate the program, causing it to run infinitely until the program crashes. I'm not sure what's causing this, and unfortunately until I fix it I can't really continue any farther with my project..

使用几个printf语句,我已将问题分解为print_table函数中的递归。由于某种原因,AST-> left似乎没有到达NULL指针来终止程序,导致它无限运行直到程序崩溃。我不确定是什么导致这种情况,不幸的是,直到我解决它,我不能继续我的项目更进一步..

2 个解决方案

#1

Let's start right in the middle:

让我们从中间开始吧:

       }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++;
  }

This is bad. You set tmp = AST, then tmp->left and tmp->right to NULL, but that also sets AST->left and AST->right to NULL, since they point to the same thing! Later on, you set AST->left = tmp, which creates a cycle, since again, AST and tmp point to the same thing, so it is equivalent to AST->left = AST. Recursing into AST->left is therefore infinite descent, AKA stack overflow.

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

#2

While the reason for the infinite recursion of your code is already given by EOF's answer, taking a look at the code I couldn't resist to tell you, that at least to me it seems, maybe you should rethink your algorithm too.

虽然你的代码无限递归的原因已经由EOF的答案给出,看看我无法抗拒的代码,至少对我而言,似乎你也应该重新考虑你的算法。

Most probably it is not numbers (int) you want to keep on the stack, but AST-fragments. Imagine expressions like 1 2 + 3 4 + * or even deeper nested ones. Changing struct snodeto:

最有可能的不是你想要保留在堆栈上的数字(int),而是AST片段。想象一下表达式如1 2 + 3 4 + *甚至更深的嵌套表达式。改变struct snodeto:

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

Your code might look something like:

您的代码可能类似于:

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;
}

Input 5 4 A 3 X will produce 3 0 4 0 5 as expected, so there should still be enough for you to work upon.

输入5 4 A 3 X将按预期生成3 0 4 0 5,因此仍有足够的时间供您使用。

Good luck on that mission.

祝你好运。

To be sure, we are talking about the same facts here. For push() and pop(), not given in your code fragments, I used the following code.

可以肯定的是,我们在这里谈论的是相同的事实。对于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;
}