将中缀转换为二叉树
Converting infix to binary tree
如何将中缀表达式转换为树？我想手动完成而不是先编程。例如，让我们看一下这个中缀表达式：
b = (x * a) - y / b * (c + d)
把这个变成树的规则是什么？或者你建议采取什么步骤来做到这一点？我在这里遇到了麻烦，因为有时这些表达式中没有明确的括号：
b = x * a - y / b * c + d
您在此处描述的问题通常称为 表达式解析，该过程通常有两个步骤：
首先，扫描，您可以在其中获取输入字符串并将其分解为一堆较小的逻辑单元，每个逻辑单元代表一个 "piece"输入。例如，给定输入字符串
b = x * a - y / b * c + d
你可能会产生这个标记序列：
[b] [=] [x] [*] [a] [-] [y] [/] [b] [*] [c] [+] [d]
这样，您就可以从 "the input is a sequence of characters" 移动到 "the input is a sequence of individual variables, operators, etc." 有很多方法可以执行此步骤，它们通常涉及进行一些手动字符串处理或使用正则表达式（如果您熟悉那些）。作为第一步，看看你是否能让这部分工作。
第二步，可能是您最关心的一步，是 解析，您在其中获取该标记序列并重构语句的含义。这通常涉及确定运算符优先级并实际构建您想要的树结构。顺便说一句，那棵树通常被称为 表达式树 或 abstract syntax tree (AST)。
有很多方法可以做到这一点。对于解析表达式，我个人的首选是 Dijkstra's shunting-yard algorithm。该算法的工作原理是维护两个堆栈并一次处理一个令牌，使用堆栈来确定应将运算符应用于什么。
如果您想查看如何执行此操作的示例，我构建了一个 truth table generator for a discrete math class that I regularly teach. You type in a logical expression, and the code scans it to get a token sequence, then uses the shunting-yard algorithm to build up an AST, which is then used to generate the truth table tool. The source code 分解，以便每个步骤单独完成，这可能是一个很好的参考。
如何将中缀表达式转换为树？我想手动完成而不是先编程。例如，让我们看一下这个中缀表达式：
b = (x * a) - y / b * (c + d)
把这个变成树的规则是什么？或者你建议采取什么步骤来做到这一点？我在这里遇到了麻烦，因为有时这些表达式中没有明确的括号：
b = x * a - y / b * c + d
您在此处描述的问题通常称为 表达式解析，该过程通常有两个步骤：
首先，扫描，您可以在其中获取输入字符串并将其分解为一堆较小的逻辑单元，每个逻辑单元代表一个 "piece"输入。例如，给定输入字符串
b = x * a - y / b * c + d
你可能会产生这个标记序列：
[b] [=] [x] [*] [a] [-] [y] [/] [b] [*] [c] [+] [d]
这样，您就可以从 "the input is a sequence of characters" 移动到 "the input is a sequence of individual variables, operators, etc." 有很多方法可以执行此步骤，它们通常涉及进行一些手动字符串处理或使用正则表达式（如果您熟悉那些）。作为第一步，看看你是否能让这部分工作。
第二步，可能是您最关心的一步，是 解析，您在其中获取该标记序列并重构语句的含义。这通常涉及确定运算符优先级并实际构建您想要的树结构。顺便说一句，那棵树通常被称为 表达式树 或 abstract syntax tree (AST)。
有很多方法可以做到这一点。对于解析表达式，我个人的首选是 Dijkstra's shunting-yard algorithm。该算法的工作原理是维护两个堆栈并一次处理一个令牌，使用堆栈来确定应将运算符应用于什么。
如果您想查看如何执行此操作的示例，我构建了一个 truth table generator for a discrete math class that I regularly teach. You type in a logical expression, and the code scans it to get a token sequence, then uses the shunting-yard algorithm to build up an AST, which is then used to generate the truth table tool. The source code 分解，以便每个步骤单独完成，这可能是一个很好的参考。