- 作者：努力学习的大一在校计算机专业学生，热爱学习和创作。目前在学习和分享：算法、数据结构、Java等相关知识。
- 博主主页： @是瑶瑶子啦
- 所属专栏: 【数据结构】：该专栏专注于数据结构知识，持续更新，每一篇内容优质，浅显易懂，不失深度！
- 近期目标：写好专栏的每一篇文章
目录
- 一、什么是中缀表达式、后缀表达式、前缀表达式
- 二、中缀转后缀
- 三、中缀转前缀
- 四、使用表达式树
一、什么是中缀表达式、后缀表达式、前缀表达式
-
中缀表达式：
中缀表达式是我们常见的数学表达式，其中运算符放置在两个操作数中间，例如：3 + 4 * 2。在中缀表达式中，还可以包含括号，用于改变运算符的优先级。 -
后缀表达式：
后缀表达式（也称为逆波兰表达式）是一种将运算符放置在操作数后面的表达式，例如：3 4 2 * 1 5 - 2 ^ / +。在后缀表达式中，所有操作符的优先级相同，而括号则不再需要。 -
前缀表达式：
前缀表达式（也称为波兰表达式）是一种将运算符放置在操作数前面的表达式，例如：+ / * 3 4 2 ^ - 1 5 2。前缀表达式和后缀表达式的计算方式相同，只是运算符的位置不同。
其中，后缀表达式和前缀表达式都是一种无歧义的表示方法，可以通过栈来快速计算。在计算机科学中，后缀表达式比较常用，因为它可以通过栈来轻松地实现表达式的计算。
一般我们所讲“算术表达式”，没有特别强调时，都是指的“中缀表达式”，也就是最常见的那种
通过后缀表达式进行计算可以按照以下步骤进行：
- 创建一个空栈，用于存储数字。
- 从左到右扫描后缀表达式的每个元素。
- 如果当前元素是数字，则将其压入栈中。
- 如果当前元素是操作符，则依次弹出栈顶的两个数字，进行相应的运算，并将结果压入栈中。
- 当后缀表达式扫描完毕后，栈中的唯一元素就是表达式的最终结果。
以下是一个示例，计算后缀表达式 “3 4 2 * 1 5 - 2 ^ / +”：
| 后缀表达式 | 操作 | 栈 |
|---|---|---|
| 3 | 压栈 | 3 |
| 4 | 压栈 | 3 4 |
| 2 | 压栈 | 3 4 2 |
| * | 弹栈计算并压栈 | 3 8 |
| 1 | 压栈 | 3 8 1 |
| 5 | 压栈 | 3 8 1 5 |
| - | 弹栈计算并压栈 | 3 8 -4 |
| 2 | 压栈 | 3 8 -4 2 |
| ^ | 弹栈计算并压栈 | 3 8 16 |
| / | 弹栈计算并压栈 | 0.1875 |
| + | 弹栈计算并压栈 | 3.1875 |
因此，后缀表达式 “3 4 2 * 1 5 - 2 ^ / +” 的计算结果为 3.1875。
二、中缀转后缀
要将算术表达式转换为逆波兰表达式，可以按照以下步骤进行：
- 创建一个空的栈，用于存储操作符。
- 从左到右扫描中缀表达式的每个元素。
- 如果当前元素是操作数，则直接输出到逆波兰表达式中。
- 如果当前元素是操作符，则进行如下操作：
- 如果该操作符为左括号 “(”，则将其压入栈中。
- 如果该操作符为右括号 “)”，则将栈中的操作符弹出并输出，直到遇到左括号为止。
- 如果该操作符为其他操作符，则根据其优先级和结合性，依次将栈中比它优先级高或等于它的操作符弹出并输出，然后将该操作符压入栈中。
- 当中缀表达式扫描完毕后，如果栈中还有操作符，则依次弹出并输出。
最终输出的结果就是逆波兰表达式。
算术表达式 a+b*(c+d/e) 转化为后缀表达式的过程如下：
| 中缀表达式 | 操作 | 栈 | 后缀表达式 |
|---|---|---|---|
| a | 输出 | 空 | a |
| + | 压栈 | + | a |
| b | 输出 | + | a b |
| * | 压栈 | + * | a b |
| ( | 压栈 | + * ( | a b |
| c | 输出 | + * ( | a b c |
| + | 压栈 | + *（ + | a b c |
| d | 输出 | + * ( + | a b c d |
| / | 压栈 | + * ( + / | a b c d |
| e | 输出 | + * ( + / | a b c d e |
| ) | 弹栈输出 | + * | a b c d e / |
| 结束 | 弹栈输出 | 空 | a b c d e / + * + |
因此，算术表达式 a+b*(c+d/e) 转化为后缀表达式为 a b c d e / + * +
三、中缀转前缀
- 将中缀表达式翻转。
- 将所有括号方向翻转，即左括号变为右括号，右括号变为左括号。
- 将翻转后的中缀表达式转化为后缀表达式。
- 再次将后缀表达式翻转，得到前缀表达式。
例如，将中缀表达式 a+b*c-d/e 转化为前缀表达式的过程如下：
- 将中缀表达式翻转：e/d-c*b+a
- 将翻转后的中缀表达式转化为后缀表达式：ed/ cb* - a+
- 再次将后缀表达式翻转，得到前缀表达式：+a -*c/b de
因此，中缀表达式 a+b*c-d/e 转化为前缀表达式为 +a -*c/b de。
四、使用表达式树
将算术表达式转换为二叉树的过程可以使用表达式树的方法实现，具体步骤如下：
- 将算术表达式转化为后缀表达式。
- 从左到右扫描后缀表达式的每个元素：
- 如果当前元素是操作数，则创建一个只包含该操作数的节点，并将该节点压入栈中。
- 如果当前元素是操作符，则创建一个只包含该操作符的节点，并从栈中弹出两个节点作为其左右子节点，再将该节点压入栈中。
- 最后栈中唯一的节点即为根节点，整个树的结构已经建立完成。
例如，将算术表达式 a+b*(c+d/e) 转化为二叉树的过程如下：
- 将算术表达式转化为后缀表达式：abcde/+*+
- 从左到右扫描后缀表达式的每个元素：
- a：创建一个只包含 a 的节点，并将该节点压入栈中。
- b：创建一个只包含 b 的节点，并将该节点压入栈中。
- c：创建一个只包含 c 的节点，并将该节点压入栈中。
- d：创建一个只包含 d 的节点，并将该节点压入栈中。
- e：创建一个只包含 e 的节点，并将该节点压入栈中。
- /：创建一个只包含 / 的节点，并从栈中弹出两个节点 e 和 d 作为其左右子节点，再将该节点压入栈中。
- +：创建一个只包含 + 的节点，并从栈中弹出两个节点 c 和 / 作为其左右子节点，再将该节点压入栈中。
- *：创建一个只包含 * 的节点，并从栈中弹出两个节点 b 和 + 作为其左右子节点，再将该节点压入栈中。
- +：创建一个只包含 + 的节点，并从栈中弹出两个节点 a 和 * 作为其左右子节点，再将该节点压入栈中。
- 根节点为最后剩余在栈中的节点 +。
因此，算术表达式 a+b*(c+d/e) 转化为的二叉树如下：文章来源：https://uudwc.com/A/20jYq
+
/ \
a *
/ \
b +
/ \
c /
/ \
d e
转换完成后，该二叉树的前序遍历对应前缀表达式，中序对应中缀表达式，后序遍历对应后缀表达式文章来源地址https://uudwc.com/A/20jYq
