用 C# 设计与实现一个四则算术运算解释器
2009-05-29 08:31:32 来源:WEB开发网实际上,整个解释器的开发,遵从“启发式 heuristic ”的原理。整个解释的过程可以分解成一条条的“规则”,我们需要做的是把规则全部“找”出来,并且把规则制定的尽可能完善。
好了,回到刚才的分析上。假设要插入的操作符不是 +,而是一个优先权比较高的 * 呢?也就是,若是 1 + 2 * 3 的话,AST 会是什么样子?
这种情况下,乘法运算符必须移动到树的右子树上,并且成为右子树的根。原右子树会成为新的右子树的左子树。
插入操作符的代码实现如下:
if (token is OpToken) {
if (root.Token is OpToken && root.RightChild == null) {
throw new ParseFailureException(
"The expression '{0} {1}' is not a valid arithmetic expression.",
root.Token.ToString(),
token.ToString()
);
}
if (root.Token is NumToken) {
Syntax newRoot = new Syntax(token);
newRoot.LeftChild = root;
root = newRoot;
return newRoot;
}
if (root.Token is OpToken) {
// Compare prioirty of the two operators
OpToken token1 = (OpToken)token;
OpToken token2 = (OpToken)root.Token;
if (token1.Prioirty <= token2.Prioirty) {
Syntax newRoot = new Syntax(token1);
newRoot.LeftChild = root;
root = newRoot;
return newRoot;
}
if (token1.Prioirty > token2.Prioirty) {
root.RightChild = Append(root.RightChild, token);
return root;
}
}
}
赞助商链接