Evaluating expression from abstract syntax tree

Question

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:

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

You can do `char c = 'A'; int ix = c - 'A'`. Or simply `c + 0` if you don't mind that the numbering doesn't start at 0. — ShellFish, May 10 '15 at 16:06
Please don't use the "code snippet" button for C code. It is only for runnable web stuff (html/JS). Use the normal code button `{}`. — Mat, May 10 '15 at 16:06
It looks like you only have numbers and operators. So in case your current node is no operator, simply returning `atoi(AST->datum)` should do the job (assuming that `AST->datum` is zero-terminated). Another thing: The code for operator `'S'` (= subtract?) of function `evaluate` looks incorrect... — Lukas Thomsen, May 10 '15 at 19:16
I had trouble copying and pasting from Unix but everthing should be fixed. So at the end of the 'evaluate' function I should change 'return AST->datum' to 'return atoi(AST->datum);' ? @LukasThomsen — etorr96, May 10 '15 at 19:19
Why are you using a tree? A stack will do. There are lots of algorithms to do this. I wrote it in 6502A assembly — Ed Heal, May 10 '15 at 19:19
I have multiple operations I have to perform on the expression and my instructor told me that the easiest way to perform these operations would be by a tree instead of a stack. @EdHeal — etorr96, May 10 '15 at 19:22
Your instructor is wrong. Look up the algorithms for converting infix to postfix and its evaluation. — Ed Heal, May 10 '15 at 19:26
I think that's kind of rude to say. We had a previous lab assignment where we only used the stack. But like I said, we have multiple operations we have to perform on the expression and this method should make them easier. @EdHeal — etorr96, May 10 '15 at 19:32
I made that change but I am getting an error that says 'error: switch quantity not an integer'. any suggestions on how to fix this? @LukasThomsen — etorr96, May 10 '15 at 19:33
@etorr96 - The shunning algorithm is good for any expression, easy to implement and good for memory usage. — Ed Heal, May 10 '15 at 19:35
Even if it is easier, this assignment was given to us again for a reason and as a student trying to learn, I'd like to practice with every possible solution. thank you for your input though. @EdHeal — etorr96, May 10 '15 at 19:38
I would have thought that your tutor would be proud that you have done research over the matter. For the record you do not need the casts on malloc return values — Ed Heal, May 10 '15 at 19:42
@etorr96: This error is not caused by the modification but the `switch ( AST->datum )` which is not an integer but an `char *`. An ugly fix for that would be `switch (AST->datum[0] )` but this assumes that the operator is always the first character of your tokens. Better build several if checks using `strcmp` as within your `isoperator` function. — Lukas Thomsen, May 10 '15 at 19:42
@LukasThomsen One would think that `isoperator(x)` would guarantee that `switch (AST->datum[0])` is valid since the only operators are represented as single-character strings. Perhaps I miss the point of the reason behind mentioning the ugly fix. — , May 11 '15 at 00:51
@etorr96 You should `return 0;` in the event that `ast->left` or `ast->right` is NULL. Aside from that, where is your `else { ... }` for non-operators? If you need help with converting a string to an integer, a good start would be [the `strtol()` function](http://en.cppreference.com/w/c/string/byte/strtol). — , May 11 '15 at 00:55
I have made this change with the 'return 0;'. I have also edited the post to something new I've tried. What is the difference between strol() and atoi? @ChronoKitsune — etorr96, May 11 '15 at 01:09
@etorr96 The difference between `strtol()` and `atoi()` is simple: what if the "number" isn't actually a number? That is, what if you end up with `"ABC" "A" "9"`? With `strtol()`, you can at least check for errors in two ways: 1) `errno` will be unset, and 2) the object to which the second argument of `strtol()` points will be a string. With `atoi()`, you cannot necessarily do that. See [the difference between `strtol()` and `atoi()`](http://ideone.com/aarpnh). — , May 11 '15 at 01:56

score 0 · Answer 1 · answered May 16 '15 at 14:38

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.

Your isoperator function needs a pointer to struct tnode

int isoperator(struct tnode *AST);

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

if (isoperator(AST->datum))

If you correcte you condition to this :

if (isoperator(AST))

It will probably works better.

Evaluating expression from abstract syntax tree

1 Answers1