如何将中缀表达式转换为树？我想手动操作而不是先编程。例如，让我们看一下这个中缀表达式：
b = (x * a) - y / b * (c + d)
将其变成树的规则是什么？或您建议采取什么步骤来做到这一点？我在这里遇到麻烦，因为有时这些表达式中没有明确的括号：
b = x * a - y / b * c + d
最佳答案
您在此处描述的问题通常称为表达式解析，并且该过程通常有两个步骤：
首先，进行扫描，将输入字符串分成多个较小的逻辑单元，每个逻辑单元代表输入的单个“部分”。例如，给定输入字符串
b = x * a - y / b * c + d
您可能会产生以下令牌序列：
[b] [=] [x] [*] [a] [-] [y] [/] [b] [*] [c] [+] [d]
这样，您可以从“输入是字符序列”变为“输入是各个变量，运算符等的序列”。有很多方法可以执行此步骤，并且通常涉及一些手动字符串处理或使用正则表达式（如果您熟悉的话）。第一步，请看是否可以使该部分正常工作。
第二步（可能是您最挂念的一步）是解析，在此步骤中，您将使用该标记序列并重新构造语句的含义。这通常涉及确定运算符的优先级，并实际构建所需的树结构。顺便说一句，该树通常称为表达式树或abstract syntax tree（AST）。
有很多方法可以做到这一点。对于解析表达式，我个人是Dijkstra's shunting-yard algorithm。该算法通过维护两个堆栈并一次处理一个令牌来工作，使用堆栈来确定应将运算符应用于什么。
如果您想查看有关此操作的示例，我为我定期教授的离散数学课程构建了truth table generator。键入逻辑表达式，然后代码对其进行扫描以获取令牌序列，然后使用调车码算法构建AST，然后将其用于生成真值表工具。 source code进行了细分，因此每个步骤都是单独完成的，这可能是一个很好的参考。