从抽象语法树评估表达式

I have an abstract syntax tree that I made from a reverse polish notation expression. The tree's nodes are all strings.

我有一个抽象的语法树,我用反向抛光表示法表达。树的节点都是字符串。

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

This is the code I have so far. For the evaluate function, I have thought about using this:

这是我到目前为止的代码。对于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;
  }
}

but I don't think this will work because I'm using strings instead of ints. what can I change on my evaluate function?

但我认为这不会起作用,因为我使用的是字符串而不是整数。我的评估功能可以改变什么?

EDIT: I've noticed the code I posted was a little messy. I've cleaned it up so it looks a little better.

编辑:我注意到我发布的代码有点乱。我把它清理干净,看起来好一点。

EDIT2:

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

I have tried getting rid of the switch statement but I am now getting a core dump. This is just something I wanted to try. I would prefer fixing my previous evaluate function

我试图摆脱switch语句但我现在正在获得核心转储。这只是我想尝试的东西。我宁愿修复我以前的评估功能

1 个解决方案

#1

Sorry I don't have sufficient reputation to comment so I will put an error that I noticed, the coredump is probably from this error.

抱歉,我没有足够的声誉来评论,所以我会发出一个我注意到的错误,coredump可能是由于这个错误。

Your isoperator function needs a pointer to struct tnode

isoperator函数需要一个指向struct tnode的指针

int isoperator(struct tnode *AST);

But you give it AST->datum which is a char * in your evaluate function:

但是你给它AST-> datum,它是你的evaluate函数中的一个char *:

if (isoperator(AST->datum))

If you correcte you condition to this :

如果你纠正你的情况:

if (isoperator(AST))

It will probably works better.

它可能会更好。

#1