• 作者:努力学习的大一在校计算机专业学生,热爱学习和创作。目前在学习和分享:算法、数据结构、Java等相关知识。
  • 博主主页: @是瑶瑶子啦
  • 所属专栏: 【数据结构】:该专栏专注于数据结构知识,持续更新,每一篇内容优质,浅显易懂,不失深度!
  • 近期目标:写好专栏的每一篇文章

目录

  • 一、什么是中缀表达式、后缀表达式、前缀表达式
  • 二、中缀转后缀
  • 三、中缀转前缀
  • 四、使用表达式树

一、什么是中缀表达式、后缀表达式、前缀表达式

  • 中缀表达式:
    中缀表达式是我们常见的数学表达式,其中运算符放置在两个操作数中间,例如:3 + 4 * 2。在中缀表达式中,还可以包含括号,用于改变运算符的优先级。

  • 后缀表达式:
    后缀表达式(也称为逆波兰表达式)是一种将运算符放置在操作数后面的表达式,例如:3 4 2 * 1 5 – 2 ^ / +。在后缀表达式中,所有操作符的优先级相同,而括号则不再需要。

  • 前缀表达式:
    前缀表达式(也称为波兰表达式)是一种将运算符放置在操作数前面的表达式,例如:+ / * 3 4 2 ^ – 1 5 2。前缀表达式和后缀表达式的计算方式相同,只是运算符的位置不同。

其中,后缀表达式和前缀表达式都是一种无歧义的表示方法,可以通过栈来快速计算。在计算机科学中,后缀表达式比较常用,因为它可以通过栈来轻松地实现表达式的计算。

一般我们所讲“算术表达式”,没有特别强调时,都是指的“中缀表达式”,也就是最常见的那种

通过后缀表达式进行计算可以按照以下步骤进行:

  1. 创建一个空栈,用于存储数字。
  2. 从左到右扫描后缀表达式的每个元素。
  3. 如果当前元素是数字,则将其压入栈中。
  4. 如果当前元素是操作符,则依次弹出栈顶的两个数字,进行相应的运算,并将结果压入栈中。
  5. 当后缀表达式扫描完毕后,栈中的唯一元素就是表达式的最终结果。

以下是一个示例,计算后缀表达式 “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。

二、中缀转后缀

要将算术表达式转换为逆波兰表达式,可以按照以下步骤进行:

  1. 创建一个空的栈,用于存储操作符。
  2. 从左到右扫描中缀表达式的每个元素。
  3. 如果当前元素是操作数,则直接输出到逆波兰表达式中。
  4. 如果当前元素是操作符,则进行如下操作:
    • 如果该操作符为左括号 “(”,则将其压入栈中。
    • 如果该操作符为右括号 “)”,则将栈中的操作符弹出并输出,直到遇到左括号为止。
    • 如果该操作符为其他操作符,则根据其优先级和结合性,依次将栈中比它优先级高或等于它的操作符弹出并输出,然后将该操作符压入栈中。
  5. 当中缀表达式扫描完毕后,如果栈中还有操作符,则依次弹出并输出。

最终输出的结果就是逆波兰表达式。

算术表达式 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 / + * +

三、中缀转前缀

  1. 将中缀表达式翻转。
  2. 将所有括号方向翻转,即左括号变为右括号,右括号变为左括号。
  3. 将翻转后的中缀表达式转化为后缀表达式
  4. 再次将后缀表达式翻转,得到前缀表达式。

例如,将中缀表达式 a+b*c-d/e 转化为前缀表达式的过程如下:

  1. 将中缀表达式翻转:e/d-c*b+a
  2. 将翻转后的中缀表达式转化为后缀表达式:ed/ cb* – a+
  3. 再次将后缀表达式翻转,得到前缀表达式:+a -*c/b de

因此,中缀表达式 a+b*c-d/e 转化为前缀表达式为 +a -*c/b de。

四、使用表达式树

将算术表达式转换为二叉树的过程可以使用表达式树的方法实现,具体步骤如下:

  1. 将算术表达式转化为后缀表达式。
  2. 从左到右扫描后缀表达式的每个元素:
    • 如果当前元素是操作数,则创建一个只包含该操作数的节点,并将该节点压入栈中。
    • 如果当前元素是操作符,则创建一个只包含该操作符的节点,并从栈中弹出两个节点作为其左右子节点,再将该节点压入栈中。
  3. 最后栈中唯一的节点即为根节点,整个树的结构已经建立完成。

例如,将算术表达式 a+b*(c+d/e) 转化为二叉树的过程如下:

  1. 将算术表达式转化为后缀表达式:abcde/+*+
  2. 从左到右扫描后缀表达式的每个元素:
    • a:创建一个只包含 a 的节点,并将该节点压入栈中。
    • b:创建一个只包含 b 的节点,并将该节点压入栈中。
    • c:创建一个只包含 c 的节点,并将该节点压入栈中。
    • d:创建一个只包含 d 的节点,并将该节点压入栈中。
    • e:创建一个只包含 e 的节点,并将该节点压入栈中。
    • /:创建一个只包含 / 的节点,并从栈中弹出两个节点 e 和 d 作为其左右子节点,再将该节点压入栈中。
    • +:创建一个只包含 + 的节点,并从栈中弹出两个节点 c 和 / 作为其左右子节点,再将该节点压入栈中。
    • *:创建一个只包含 * 的节点,并从栈中弹出两个节点 b 和 + 作为其左右子节点,再将该节点压入栈中。
    • +:创建一个只包含 + 的节点,并从栈中弹出两个节点 a 和 * 作为其左右子节点,再将该节点压入栈中。
  3. 根节点为最后剩余在栈中的节点 +。

因此,算术表达式 a+b*(c+d/e) 转化为的二叉树如下:

+ / \a * / \b + / \c / / \d e

转换完成后,该二叉树的前序遍历对应前缀表达式中序对应中缀表达式后序遍历对应后缀表达式