Evaluation

To evaluate the parse tree we are going to write a recursive function. But before we get started, let us try and see what observations we can make about the structure of the tree we get as input. Try printing out some expressions using your program from the previous chapter. What do you notice?

  1. lispy> * 10 (+ 1 51)
  2. >
  3.   regex
  4.   operator|char:1:1 '*'
  5.   expr|number|regex:1:3 '10'
  6.   expr|>
  7.     char:1:6 '('
  8.     operator|char:1:7 '+'
  9.     expr|number|regex:1:9 '1'
  10.     expr|number|regex:1:11 '51'
  11.     char:1:13 ')'
  12.   regex

One observation is that if a node is tagged with number it is always a number, has no children, and we can just convert the contents to an integer. This will act as the base case in our recursion.

If a node is tagged with expr, and is not a number, we need to look at its second child (the first child is always '(') and see which operator it is. Then we need to apply this operator to the evaluation of the remaining children, excluding the final child which is always ')'. This is our recursive case. This also needs to be done for the root node.

When we evaluate our tree, just like when counting the nodes, we’ll need to accumulate the result. To represent this result we’ll use the C type long which means a long integer.

To detect the tag of a node, or to get a number from a node, we will need to make use of the tag and contents fields. These are string fields, so we are going to have to learn a couple of string functions first.

atoiConverts a char to a int.
strcmpTakes as input two char and if they are equal it returns 0.
strstrTakes as input two char* and returns a pointer to the location of the second in the first, or 0 if the second is not a sub-string of the first.

We can use strcmp to check which operator to use, and strstr to check if a tag contains some substring. Altogether our recursive evaluation function looks like this.

  1. long eval(mpc_ast_t* t) {
  3.   /* If tagged as number return it directly. */
  4.   if (strstr(t->tag, "number")) {
  5.     return atoi(t->contents);
  6.   }
  8.   /* The operator is always second child. */
  9.   char* op = t->children[1]->contents;
  11.   /* We store the third child in `x` */
  12.   long x = eval(t->children[2]);
  14.   /* Iterate the remaining children and combining. */
  15.   int i = 3;
  16.   while (strstr(t->children[i]->tag, "expr")) {
  17.     x = eval_op(x, op, eval(t->children[i]));
  18.     i++;
  19.   }
  21.   return x;
  22. }

We can define the eval_op function as follows. It takes in a number, an operator string, and another number. It tests for which operator is passed in, and performs the corresponding C operation on the inputs.

  1. /* Use operator string to see which operation to perform */
  2. long eval_op(long x, char* op, long y) {
  3.   if (strcmp(op, "+") == 0) { return x + y; }
  4.   if (strcmp(op, "-") == 0) { return x - y; }
  5.   if (strcmp(op, "*") == 0) { return x * y; }
  6.   if (strcmp(op, "/") == 0) { return x / y; }
  7.   return 0;
  8. }