用 C# 设计与实现一个四则算术运算解释器

核心提示： 插入数字 NumToken 怎么处理呢？ 这个很简单，NumToken总是成为右子树，用 C# 设计与实现一个四则算术运算解释器(6)，代码如下（这里用到了线性递归，可以换成用尾端递归来提高效率）：if(tokenisNumToken){if(root.TokenisOpToken){if

插入数字 NumToken 怎么处理呢？ 这个很简单，NumToken总是成为右子树。代码如下（这里用到了线性递归，可以换成用尾端递归来提高效率）：

if　(token　is　NumToken)　{
　
　　if　(root.Token　is　OpToken)　{
　
　　　　if　(root.RightChild　==　null)　{
　
　　　　　　Syntax　newNode　=　new　Syntax(token);
　　　　　　root.RightChild　=　newNode;
　
　
　　　　　　return　root;
　
　　　　}　else　{
　
　　　　　　root.RightChild　=　this.Append(root.RightChild,　token);
　
　　　　　　return　root;
　
　　　　}
　
　　}　else　{
　
　　　　throw　new　ParseFailureException(
　　　　　　"The　expression　'{0}　{1}'　is　not　a　valid　arithmetic　expression.",
　　　　　　root.Token.ToString(),
　　　　　　token.ToString()
　　　　);
　
　　}
}

四、求运算结果

当 AST 树创建出来后，求运算结果就很简单了，用线性递归即可。

求值（根）

若是遇到 NumToken，返回值

若是遇到 OpToken +，返回 求值（左子树） +　求值（右子树）

若是遇到 OpToken －，返回 求值（左子树） -　求值（右子树）

….

代码如下：

private　double　Eval(Syntax　root)　{
　
　　if　(root　==　null)　{
　　　　return　0;
　　}　

　　if　(root.Token　is　NumToken)　{
　　　　NumToken　token1　=　(NumToken)root.Token;
　　　　return　token1.Value;
　　}
　
　　if　(root.Token　is　OpToken)　{
　　　　OpToken　token1　=　(OpToken)root.Token;
　
　　　　if　(root.RightChild　==　null　&&　root.LeftChild　==　null)　{
　　　　　　throw　new　ParseFailureException(
　　　　　　　　"The　expression　'{0}'　cannot　be　a　value.",
　　　　　　　　root.Token.ToString()
　　　　　　);
　　　　}　else　{
　
　　　　　　double　lvalue　=　this.Eval(root.LeftChild);
　　　　　　double　rvalue　=　this.Eval(root.RightChild);
　
　　　　　　switch　(token1.Value)　{
　
　　　　　　　　case　Op.Plus:
　　　　　　　　　　return　lvalue　+　rvalue;
　
　　　　　　　　case　Op.Minus:
　　　　　　　　　　return　lvalue　-　rvalue;
　
　　　　　　　　case　Op.Multiply:
　　　　　　　　　　return　lvalue　*　rvalue;
　
　　　　　　　　case　Op.Divide:
　　　　　　　　　　return　lvalue　/　rvalue;
　
　　　　　　　　default:
　　　　　　　　　　throw　new　ParseFailureException(
　　　　　　　　　　　　"The　expression　'{0}　{1}　{2}'　cannot　be　a　value.",
　　　　　　　　　　　　root.LeftChild.ToString(),
　　　　　　　　　　　　root.Token.ToString(),
　　　　　　　　　　　　root.RightChild.ToString()
　　　　　　　　　　);
　　　　　　}
　　　　}
　　}
　
　　throw　new　ParseFailureException("Unrecognized　token:　"　+　
　　　　　　　root.Token.ToString());
}

后记：

这个解释器还很原始。需要添加的功能有：

1、支持一元操作符 - 和 +，它们将具有最高优先权

2、支持括号。

3、支持变量，也即需要一个 Local Variable Table。。。

比如，能够理解指令 var delta = 4 * 4 - 4 * 1 * 3，以及新的指令 2 * delta；

4、支持定义 lambda 函数。

比如，能够理解指令 let pow x = x * x，以及新的指令 pow (3)。

图是用 MS Word 2007 画的，呵。