【数据结构】超详细讲解：算术表达式转化为后缀表达式、前缀表达式、表达式树的构建

青旅半醒 2023-09-26 22:12 105阅读 0赞

![在这里插入图片描述][b88c49c5b7e04dacaaed7cf2fc928687.gif_pic_center]

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

![在这里插入图片描述][b8fa5a1a3c5441ae83a3598a7d6353e5.png]

### 目录 ###

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

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

*  ***中缀表达式：***  
    中缀表达式是我们常见的数学表达式，其中**运算符放置在两个操作数中间**，例如：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 ^ / +`”：

<table> 
 <thead> 
  <tr> 
   <th>后缀表达式</th> 
   <th>操作</th> 
   <th>栈</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>3</td> 
   <td>压栈</td> 
   <td>3</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>压栈</td> 
   <td>3 4</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>压栈</td> 
   <td>3 4 2</td> 
  </tr> 
  <tr> 
   <td>*</td> 
   <td>弹栈计算并压栈</td> 
   <td>3 8</td> 
  </tr> 
  <tr> 
   <td>1</td> 
   <td>压栈</td> 
   <td>3 8 1</td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td>压栈</td> 
   <td>3 8 1 5</td> 
  </tr> 
  <tr> 
   <td>-</td> 
   <td>弹栈计算并压栈</td> 
   <td>3 8 -4</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>压栈</td> 
   <td>3 8 -4 2</td> 
  </tr> 
  <tr> 
   <td>^</td> 
   <td>弹栈计算并压栈</td> 
   <td>3 8 16</td> 
  </tr> 
  <tr> 
   <td>/</td> 
   <td>弹栈计算并压栈</td> 
   <td>0.1875</td> 
  </tr> 
  <tr> 
   <td>+</td> 
   <td>弹栈计算并压栈</td> 
   <td>3.1875</td> 
  </tr> 
 </tbody> 
</table>

因此，后缀表达式 “3 4 2 \* 1 5 - 2 ^ / +” 的计算结果为 3.1875。

# 二、中缀转后缀 #

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

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

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

算术表达式 a+b\*(c+d/e) 转化为后缀表达式的过程如下：

<table> 
 <thead> 
  <tr> 
   <th>中缀表达式</th> 
   <th>操作</th> 
   <th>栈</th> 
   <th>后缀表达式</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>a</td> 
   <td>输出</td> 
   <td>空</td> 
   <td>a</td> 
  </tr> 
  <tr> 
   <td>+</td> 
   <td>压栈</td> 
   <td>+</td> 
   <td>a</td> 
  </tr> 
  <tr> 
   <td>b</td> 
   <td>输出</td> 
   <td>+</td> 
   <td>a b</td> 
  </tr> 
  <tr> 
   <td>*</td> 
   <td>压栈</td> 
   <td>+ *</td> 
   <td>a b</td> 
  </tr> 
  <tr> 
   <td>(</td> 
   <td>压栈</td> 
   <td>+ * (</td> 
   <td>a b</td> 
  </tr> 
  <tr> 
   <td>c</td> 
   <td>输出</td> 
   <td>+ * (</td> 
   <td>a b c</td> 
  </tr> 
  <tr> 
   <td>+</td> 
   <td>压栈</td> 
   <td>+ *（ +</td> 
   <td>a b c</td> 
  </tr> 
  <tr> 
   <td>d</td> 
   <td>输出</td> 
   <td>+ * ( +</td> 
   <td>a b c d</td> 
  </tr> 
  <tr> 
   <td>/</td> 
   <td>压栈</td> 
   <td>+ * ( + /</td> 
   <td>a b c d</td> 
  </tr> 
  <tr> 
   <td>e</td> 
   <td>输出</td> 
   <td>+ * ( + /</td> 
   <td>a b c d e</td> 
  </tr> 
  <tr> 
   <td>)</td> 
   <td>弹栈输出</td> 
   <td>+ *</td> 
   <td>a b c d e /</td> 
  </tr> 
  <tr> 
   <td>结束</td> 
   <td>弹栈输出</td> 
   <td>空</td> 
   <td>a b c d e / + * +</td> 
  </tr> 
 </tbody> 
</table>

因此，算术表达式 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

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

[b88c49c5b7e04dacaaed7cf2fc928687.gif_pic_center]: https://img-blog.csdnimg.cn/b88c49c5b7e04dacaaed7cf2fc928687.gif#pic_center
[Link 1]: https://blog.csdn.net/Yaoyao2024?spm=1011.2559.3001.5343
[Link 2]: https://blog.csdn.net/yaoyao2024/category_12256535.html
[b8fa5a1a3c5441ae83a3598a7d6353e5.png]: https://img-blog.csdnimg.cn/b8fa5a1a3c5441ae83a3598a7d6353e5.png