将中缀表达式转换为二叉树（C语言实现）

Question

我需要将一个中缀表达式解析成二叉树。

该表达式为:

 (((x1 + 5.12) ∗ (x2 − 7.68))/x3) 

我实在不知道如何解释这个表达。有人知道该如何处理吗？

- Jacob

---

@OmidCompSCI，他可能是指将表达式构建成 AST。 - bipll

@bipll 哦，那样会更有意义一些。 - Omid CompSCI

Answer 1

您的任务并不太难，首先需要了解 符号类型，然后再了解表达式解析。

一般来说，要解析和计算一个（中缀）表达式，需要执行以下步骤：

• 读取并标记它，即将每个符号分类为：操作数、运算符等等。

• 从中缀表达式转换为二叉表达式树：通常使用类似Shunting yard 算法的算法来完成。

• 创建一个语法，定义运算优先级和允许严格的¹ 表达式计算顺序。

在中缀表达式中写的表达式稍微难以解析，这就是为什么它们通常会被转换为更加“机器友好”的版本，例如（逆）波兰式表示法，其中提供了一些优点，其中之一是消除了括号的需要。

因此，您可以看到这大致上是整个过程的全部内容，而您的任务是其中的一部分。以下是用于 2 * 3 / ( 2 – 1 ) + 5 * ( 4 – 1 ) 的二叉表达式树可视化图：

这里有更多关于这个主题的内容，以及一个在 C++ 中的示例实现。

---

^{1. 在您的情况下遵守代数规则。}

- Ziezi