中缀表达式求值讲解
🎈 作者：Linux猿
🎈 简介：CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！
🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬
在前面的文章中我们已经讲解过栈的用法，本节要讲的内容是表达式求值问题，需要借助栈的辅助来完成。表达式求值中中缀表达式求值是比较常见的求值问题，如求表达式3 + （2 * 3 + 21）*2的值。在历年考研真题中经常以填空题的形式出现，接下来就开始我们的讲解吧！
中缀表达式：是我们通常理解的一种算术或逻辑公式表示方法， 操作符是以中缀形式处于操作数的中间。
表达式求值中包含操作符和操作数，需要借助两个栈分别用来存放操作符和操作数。
1、依次遍历表达式，遇到操作数压入到操作数栈；
2、当遇到操作符时，判断当前操作符与栈顶操作符的优先级。如果当前操作符的优先级大于栈顶操作符优先级，那么把当前操作符压入操作符栈中；否则在操作数栈中弹出两个操作数，弹出的第一个操作数为运算的右值，把运算之后的数值压入操作数栈中。
3、遇到右括号的时候，弹出操作符和操作数运算，将运算的结果压入到操作数中，一直计算，直到遇到左括号终止。
4、遍历完表达式之后，如果操作符栈中有值，那么弹出操作数栈的两个数进行运算，将运算的结果压入操作数栈中，重复步骤四。
5、直到操作符栈为空或者操作数栈中只剩下一个数。
假设有表达式：
9 + 4 *（ 2 + 6 / 3 ）- 5
解题步骤如下：
| 步骤 |
描述 |
操作 数栈 |
操作 符栈 |
| 1 |
首先遇到9，把9压入操作数栈 |
9 |
|
| 2 |
遇到+,把+压入操作符栈 |
9 |
+ |
| 3 |
遇到4，把4压入操作数栈 |
9,4 |
+ |
| 4 |
遇到*，优先级大于+，压入操作符栈 |
9,4 |
+,* |
| 5 |
遇到（，压入操作符栈 |
9,4 |
+,*,( |
| 6 |
遇到2，压入操作数栈中 |
9,4,2 |
+,*,( |
| 7 |
遇到+，优先级大于（，压入操作符栈 |
9,4,2 |
+,*,(,+ |
| 8 |
遇到 6，压入操作数栈 |
9,4,2,6 |
+,*,(,+ |
| 9 |
遇到/,压入操作符栈 |
9,4,2,6 |
+,*,(,+,/ |
| 10 |
遇到3，压入操作数栈 |
9,4,2,6,3 |
+,*,(,+,/ |
| 11 |
遇到），弹出操作符栈顶/，弹出两个操作数进行运算6/3=2，把2压入操作数栈 |
9,4,2,2 |
+,*,(,+ |
| 12 |
弹出操作符栈顶+，弹出两个操作数进行运算2+2=4，把4压入操作数栈中 |
9,4,4 |
+,*( |
| 13 |
弹出操作符栈（ |
9,4,4 |
+,* |
| 14 |
遇到-，优先级小于*，弹出操作符栈顶*，弹出两个操作数进行运算4*4=16，把16压入操作数栈 |
9,16 |
+ |
| 15 |
弹出操作符栈顶+，弹出两个操作数进行运算9+16=25，把25压入操作数栈中 |
25 |
|
| 16 |
将-压入操作符栈中 |
25 |
- |
| 17 |
遇到5，将5压入操作数栈中 |
25,5 |
- |
| 18 |
表达式遍历结束，操作符栈中有值，继续弹出操作符栈顶-，弹出两个操作数进行运算25-5=20，把20压入操作数栈中，此时操作数栈中剩下一个数据即为最终数据 |
20 |
对于表达式求值问题，需要多练多写多模拟，记住解题思路。在工大历年考研真题中，经常以填空题的形式出现，当然还有后缀表达式求值问题，中缀转后缀问题，都可以借助栈的辅助来求解，后面我们会对另外两种进行讲解，敬请期待！
大家有不理解的可以在评论区评论哦！
CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！
欢迎小伙伴们点赞👍、收藏⭐、留言💬
- 点赞
- 收藏
- 关注作者
评论（0）