- 作者:努力学习的大一在校计算机专业学生,热爱学习和创作。目前在学习和分享:算法、数据结构、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) 转化为的二叉树如下:
+ / \a * / \b + / \c / / \d e
转换完成后,该二叉树的前序遍历对应前缀表达式,中序对应中缀表达式,后序遍历对应后缀表达式