5

我有一个由反向波兰符号表达式制作的抽象语法树。树的节点都是字符串。

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

这是我到目前为止的代码。对于评估功能，我考虑过使用这个：

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 语句，但现在我得到了核心转储。这只是我想尝试的。我宁愿修复我以前的评估功能

4

1 回答 1

0

抱歉，我没有足够的声誉来发表评论，所以我会提出一个我注意到的错误，核心转储可能来自这个错误。

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

int isoperator(struct tnode *AST);

但是你给它 AST->datum 这是你评估函数中的一个 char * ：

if (isoperator(AST->datum))

如果你更正你的条件：

if (isoperator(AST))

它可能会更好。

于 2015-05-16T14:38:16.740 回答