从抽象语法树评估表达式

Question

我有一个由逆波兰表达式构建的抽象语法树。该树的节点都是字符串。

#include <stdlib.h>
#include <ctype.h>
#include <stdio.h>
#include <string.h>

struct snode 
{
  char *datum;
  struct snode* bottom;
};

struct tnode
{
  char *datum;
  struct tnode* left;
  struct tnode*right;
};

struct snode* 
push(struct snode* stack, char *x) {
  struct snode *S = (struct snode*)malloc(sizeof(struct snode));
  S->datum = (char *)malloc(strlen(x) + 1);
  strcpy(S->datum, x);
  S->bottom = stack;
  return S;
}

void
pop(struct snode **stack) {
  struct snode *S;
  if (*stack == NULL)
    return;

  S = (*stack)->bottom;
  free(*stack);
  *stack = S;
}

char *
peek(struct snode* stack){
  return stack->datum;
}


struct tnode*
create_node(char *x){
  struct tnode* tmp = (struct tnode*)malloc(sizeof(struct tnode));
  tmp->datum = (char *)malloc(strlen(x) + 1);
  strcpy(tmp->datum, x);
  tmp->right = NULL;
  tmp->left = NULL;
  return tmp;
}

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

int
is_operator(char *tok)
{
  return !strcmp(tok, "A") || !strcmp(tok, "S") || !strcmp(tok, "X") || !strcmp(tok, "D") || !strcmp(tok, "M");
}


struct tnode*
build_tree(struct snode **S)
{

  struct tnode* root;
  if (*S == NULL)
    return NULL;

  char *top = peek(*S);

  if (is_operator(top))
    {
      root = create_node(top);
      pop(S); 
      root->right = build_tree(S);
      pop(S);
      root->left = build_tree(S);
      return root;
    } 

  root = create_node(top);

  return root;
}


int
isoperator(struct tnode *AST)
{
  return !strcmp(AST->datum, "A") || !strcmp(AST->datum, "S") || !strcmp(AST->datum, "X") || !strcmp(AST->datum, "D") || !strcmp(AST->datum, "M");
}


int
main(int argc,  char *argv[])
{

  int i = 1;
  struct tnode *tree = NULL;
  struct snode *stack = NULL;

  char *value;
  while (argv[i]!= NULL)
    {
      value = argv[i];
      stack = push(stack, value);
      i++;
    }


  tree =  build_tree(&stack);
  print_table(tree);
  printf("\n");

  return EXIT_SUCCESS;
}

这是我目前的代码。对于 evaluate 函数，我的想法是使用以下方法：

int evaluate( struct tnode* AST )
{
  int x, y, z;
  if ( AST != NULL ){
    if (isoperator(AST->datum)){
          x = evaluate( AST->left);
          y = evaluate( AST->right );
          switch ( AST->datum )
            {
            case 'A':
              z = x + y;
              break;
            case 'S':
              z = x - y;
              break;
            case 'X':
              z = x * y;
              break;
            case 'D':
              z = x / y;
              break;
            case 'M':
              z = x % y;
              break;
            }
          return z;
        }

    return AST->datum;
  }
}

但我认为这样不行，因为我正在使用字符串而不是整数。我的评估函数应该怎么改？

编辑：我注意到我发布的代码有点乱。我已经清理了一下，现在看起来好多了。

编辑2：

int evaluate( struct tnode* AST )
{
  int x, y, z;
  if ( AST != NULL ){
    if (isoperator(AST->datum)){
      x = evaluate( AST->left);
      y = evaluate( AST->right );
      if(strcmp(AST->datum,"A")==0){
        z = x + y;
      }else if(strcmp(AST->datum,"S")==0){
        z = x -  y;
      }else if(strcmp(AST->datum,"X")==0){
        z = x * y;
      }else if(strcmp(AST->datum,"D")==0){
        z = x / y;
      }else if(strcmp(AST->datum,"M")==0){
        z = x % y;
      }
      return z;
     }
    return atoi(AST->datum);
    }
  return 0;
}

我曾尝试去掉switch语句，但现在程序出现了核心转储错误。这只是我想尝试的一件事。我更愿意修复之前的evaluate函数。

- etorr96

---

请不要在 C 代码中使用“代码片段”按钮。它仅适用于可运行的 Web 内容（HTML/JS）。请使用普通的代码按钮 {}。 - Mat

看起来你只有数字和运算符。所以如果当前的节点不是运算符，简单地返回 atoi(AST->datum) 应该可以解决问题（假设 AST->datum 是以零结尾的）。另一件事：函数 evaluate 的运算符'S'（= 减法？）的代码似乎有误... - Lukas Thomsen

你为什么要使用树？用栈就可以了。有很多算法可以做到这一点。我用6502A汇编语言写了它。 - Ed Heal

我需要对表达式执行多个操作，我的导师告诉我，最简单的方法是使用树而不是堆栈来执行这些操作。@EdHeal - etorr96

@etorr96 strtol()和atoi()之间的区别很简单：如果“数字”实际上不是数字怎么办？也就是说，如果你最终得到的是"ABC" "A" "9"这样的字符串，使用strtol()，你至少可以通过两种方式检查错误：1）errno将未设置，2）strtol()的第二个参数指向的对象将是一个字符串。但是，使用atoi()，你不能保证这一点。请参见strtol()和atoi()之间的区别。 - user539810

Answer 1

抱歉，我的声望不足以发表评论，所以我会指出我注意到的一个错误，核心转储可能来自于这个错误。

您的isoperator函数需要一个指向tnode结构体的指针。

int isoperator(struct tnode *AST);

但是在您的评估函数中，您将AST-> datum赋值为char *：

if (isoperator(AST->datum))

如果你将条件更正为：

if (isoperator(AST))

它可能会更好地运行。

- ar-ms