title: Evaluating expression from abstract syntax tree
body: <p>I have an abstract syntax tree that I made from a reverse polish notation expression. The tree's nodes are all strings. </p>
  
  <pre><code>#include &lt;stdlib.h&gt;
  #include &lt;ctype.h&gt;
  #include &lt;stdio.h&gt;
  #include &lt;string.h&gt;
  
  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-&gt;datum = (char *)malloc(strlen(x) + 1);
    strcpy(S-&gt;datum, x);
    S-&gt;bottom = stack;
    return S;
  }
  
  void
  pop(struct snode **stack) {
    struct snode *S;
    if (*stack == NULL)
      return;
  
    S = (*stack)-&gt;bottom;
    free(*stack);
    *stack = S;
  }
  
  char *
  peek(struct snode* stack){
    return stack-&gt;datum;
  }
  
  
  struct tnode*
  create_node(char *x){
    struct tnode* tmp = (struct tnode*)malloc(sizeof(struct tnode));
    tmp-&gt;datum = (char *)malloc(strlen(x) + 1);
    strcpy(tmp-&gt;datum, x);
    tmp-&gt;right = NULL;
    tmp-&gt;left = NULL;
    return tmp;
  }
  
  void
  print_table(struct tnode *AST){
    if(AST !=NULL){
      printf("(");
      print_table(AST-&gt;left);
      printf("%s", AST-&gt;datum);
      print_table(AST-&gt;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-&gt;right = build_tree(S);
        pop(S);
        root-&gt;left = build_tree(S);
        return root;
      } 
  
    root = create_node(top);
  
    return root;
  }
  
  
  int
  isoperator(struct tnode *AST)
  {
    return !strcmp(AST-&gt;datum, "A") || !strcmp(AST-&gt;datum, "S") || !strcmp(AST-&gt;datum, "X") || !strcmp(AST-&gt;datum, "D") || !strcmp(AST-&gt;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(&amp;stack);
    print_table(tree);
    printf("\n");
  
    return EXIT_SUCCESS;
  }
  </code></pre>
  
  <p>This is the code I have so far. For the evaluate function, I have thought about using this:</p>
  
  <pre><code>int evaluate( struct tnode* AST )
  {
    int x, y, z;
    if ( AST != NULL ){
      if (isoperator(AST-&gt;datum)){
            x = evaluate( AST-&gt;left);
            y = evaluate( AST-&gt;right );
            switch ( AST-&gt;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-&gt;datum;
    }
  }
  </code></pre>
  
  <p>but I don't think this will work because I'm using strings instead of ints. what can I change on my evaluate function?</p>
  
  <p>EDIT: I've noticed the code I posted was a little messy. I've cleaned it up so it looks a little better.</p>
  
  <p>EDIT2:</p>
  
  <pre><code>int evaluate( struct tnode* AST )
  {
    int x, y, z;
    if ( AST != NULL ){
      if (isoperator(AST-&gt;datum)){
        x = evaluate( AST-&gt;left);
        y = evaluate( AST-&gt;right );
        if(strcmp(AST-&gt;datum,"A")==0){
          z = x + y;
        }else if(strcmp(AST-&gt;datum,"S")==0){
          z = x -  y;
        }else if(strcmp(AST-&gt;datum,"X")==0){
          z = x * y;
        }else if(strcmp(AST-&gt;datum,"D")==0){
          z = x / y;
        }else if(strcmp(AST-&gt;datum,"M")==0){
          z = x % y;
        }
        return z;
       }
      return atoi(AST-&gt;datum);
      }
    return 0;
  }
  </code></pre>
  
  <p>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</p>