用 C# 设计与实现一个四则算术运算解释器
2009-05-29 08:31:32 来源:WEB开发网插入数字 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 画的,呵。
赞助商链接