栈的应用之中缀表达式转后缀表达式，以及后缀表达式的读取(超级白话版)
栈的应用之表达式
中缀转后缀表达式
首先，笔者先说下中缀表达式转后缀表达式的规则
- 遇到字母直接输出
- 遇到加减乘除首先看栈中有没有运算符，没有的话直接放在栈中，有的话则比较当前元素和栈顶元素的优先级。其实这里笔者有个小技巧。扫描的运算符如果优先级高于栈顶元素则直接放入。如果优先级低于栈顶元素则先出栈，再入栈。当我们遇到加减，或乘除这种同级的时你就看下他们在表达式中的位置，就能决定谁的优先级高
- 遇到左半边括号就直接输入栈中
- 遇到右半边括号则把栈中的元素一直输出到做括号位置==（包括左括号）==
- 等全部都结束了依次输出栈中的符号
话不多说，我们来看一下具体的例子
比如说我们要算 a+b-a*((c+d)/e-f)+g
| 步骤 | 扫描项 | 操作 | 栈内内容 | 输出的内容 |
|---|---|---|---|---|
| 01 | a | 直接输出 | a | |
| 02 | + | 因为此时栈中无运算符，所以直接放入栈中 | + | a |
| 03 | b | 直接输出 | + | ab |
| 04 | - | 减号的优先级其实和加号一样，但从表达式中明显可以看出，加号先输出 | - | ab+ |
| 05 | a | 直接输出 | - | ab+a |
| 06 | * | 因为优先级高于-号，直接进栈 | -* | ab+a |
| 07 | ( | 看到右括号则直接将其放入栈中 | -*( | ab+a |
| 08 | ( | 直接进栈 | -*(( | ab+a |
| 09 | c | 直接输出 | -*(( | ab+ac |
| 10 | + | 因为栈顶元素为右括号，所以直接进栈 | -*((+ | ab+ac |
| 11 | d | 直接输出 | -*((+ | ab+acd |
| 12 | ) | 栈中元素一直输出到第一个右括号 | -*( | ab+acd+ |
| 13 | / | 此时栈顶元素为右括号，所以直接输入 | -*(/ | ab+acd+ |
| 14 | e | 直接输出 | -*(/ | ab+acd+e |
| 15 | - | 优先级小于栈顶元素的除号，所以除号出栈，减号进栈 | -*(- | ab+acd+e/ |
| 16 | f | 直接输出 | -*(- | ab+acd+e/f |
| 17 | ) | 栈中元素一直输出到第一个右括号 | -* | ab+acd+e/f- |
| 18 | + | 优先级比栈顶乘号小。所以乘号出栈，出栈后-也是小于+，所以减号也出栈，加号进栈 | + | ab+acd+e/f-*- |
| 19 | g | 直接输出 | + | ab+acd+e/f-*-g |
| 20 | 无 | 栈内元素全部出栈 | ab+acd+e/f-*-g+ |
读后缀表达式
规则
遇到字母直接进栈，遇到运算符则连着出栈两个字母并运算
还是上题的后缀表达式 ab+acd+e/f-*-g+
| 步骤 | 扫描项 | 操作 | 栈内内容 |
|---|---|---|---|
| 01 | a | 直接进栈 | a |
| 02 | b | 直接进栈 | ab |
| 03 | + | ab出栈，并计算结果 r1=a+b，将r1进栈 | r1 |
| 04 | a | 直接进栈 | r1 a |
| 05 | c | 直接进栈 | r1 a c |
| 06 | d | 直接进栈 | r1 a c d |
| 07 | + | cd出栈，并计算c+d的结果r2,r2进栈 | r1 a r2 |
| 08 | e | 直接进栈 | r1 a r2 e |
| 09 | / | r2,e出栈，并计算r2/e=r3 | r1 a r3 |
| 10 | f | 直接进栈 | r1 a r3 f |
| 11 | - | r3,f出栈，并计算结果r4,并进栈 | r1 a r4 |
| 12 | * | a,r4出栈，并计算结果r5,并进栈 | r1 r5 |
| 13 | - | r1,r5出栈，并计算r1-r5=r6,r6进栈 | r6 |
| 14 | g | 直接进栈 | r6 g |
| 15 | + | r6,g出栈，并计算r6+g=r7,r7进栈 | r7 |
《新程序员》：云原生和全面数字化实践 
50位技术专家共同创作，文字、视频、音频交互阅读