问编写生成解析树的代码

EN

简单的解决方法是将表达式转换为后缀表示法(abcef/*++) &然后参考这个问题的答案(http://stackoverflow.com/questions/423898/postfix-notation-to-expression-tree)，将后缀表达式转换为树。

这是面试官所期望的:)

从定义语言开始。没有人可以为没有很好定义的语言实现解析器或编译器。您给出一个示例：'a+(b+c*(e/f)+d)*g'，它应该会触发以下问题：

1. 是一种语言，可以是单个表达式，也可以有多个语句(用';‘或许？
2. 什么是'a'，'b'，...“G”代币？它是可变的吗？变量的语法是什么？它是一个类似C的变量，还是像你的例子所暗示的那样，它是一个单一的字母数字字符。
3. 在你的例子中有3个二进制表达式。就这些吗？该语言是否也支持'-‘。您的语言是否支持逻辑和逐位operators?
4. Does语言支持数字文字？仅整型？双倍?该语言是否支持字符串文字？你引用的字符串literals?
5. Syntax对于comments?
6. Which运算符有优先权吗？“*”运算符是否像示例中那样优先于“+”？操作数的计算是从右到左还是从左到右？
7. Any Pre-processing?

一旦您对语言语法有了良好的定义，就可以从实现记号赋予器开始。标记器获取字符流并生成标记列表。在上面的示例中，每个字符都是一个标记，但在var*12 (var power 12)中有3个标记：'var‘、'*’和'12‘。如果允许使用正则表达式，则可以使用正则表达式完成这一部分的解析。

接下来，有一个函数通过类型来标识每个令牌:是操作符，还是变量，数字文字，字符串文字等。将所有内容打包到一个名为NextToken的方法中，该方法返回一个令牌及其类型。

最后，开始解析。在您的示例中，解析树的根将是一个带有'+‘运算符的节点(它优先于'')。左边的孩子是一个变量标记'a‘，右边的孩子是一个带有根元素'’标记的树。递归工作。

每当您打算编写解析器时，要问的主要问题是您是想手动完成，还是使用解析器生成器框架。

在这种情况下，我会说这是一个很好的练习，把它全部写出来。

从树本身的良好表示开始。这将是你的算法的输出。例如，这可能是一个对象集合，其中一个对象类型可以表示一个“标签”，如示例中的a、b和c。其他人可以代表数字。然后，您可以定义运算符的表示形式，例如，+是一个二元运算符，它将有两个子对象，分别表示左子表达式和右子表达式。

下一步是实际的解析器，我建议使用一个经典的递归解析器。描述这一点并提供标准伪代码实现的一个文本是由Theodore Norvell编写的文本