求值

为了解析求值前面生成的语法树，我们需要写一个递归函数。但是在开始之前，我们先观察一下树的结构。使用上一章的程序打印一些表达式的解析结果，你能观察到什么？

  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

首先我们注意到，有 number 标签的节点一定是一个数字，并且没有孩子节点。我们可以直接将其转换为一个数字。这将是递归函数中的基本情况。

如果一个节点有 expr 标签，但没有 number 标签，我们需要看他的第二个孩子节点是什么操作符(第一个孩子节点永远是 ( 字符)。然后我们需要使用这个操作符来对后面的孩子节点进行求值。当然，也不包括最后的 ) 节点。这就是所谓的递归的情况啦。

在对语法树进行求值的时候，正如前面编写的 number_of_nodes 函数，需要保存计算的结果。在这里，我们使用 C 语言中 long 类型(长整形)。

另外，为了检测节点的类型，或是获得节点中保存的数值，我们会用到节点中的 tag 和 contents 字段。这些字段都是字符串类型的，所以需要用到一些辅助性的库函数：

函数名 作用
atoi 将 char* 转化为 long 型
strcmp 接受两个 char* 参数，比较他们是否相等，如果相等就返回 0
strstr 接受两个 char*，如果第一个字符串包含第二个，返回其在第一个中首次出现的位置的指针，否则返回 0

我们可以使用 strcmp 来检查应该使用什么操作符，并使用 strstr 来检测 tag 中是否含有某个字段。有了这些基础，我们的递归求值函数就可以写出来啦：

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

其中，eval_op 函数的定义如下。它接受一个数字，一个操作符，和另一个数字。它检测操作符的类型，对其进行相应的计算，并将结果返回。

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