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

实际上，整个解释器的开发，遵从“启发式 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;
　　　　}
　　}
}