03 利用栈进行中缀表达式计算

运算符优先级

​​​​
栈内运算符加减乘除取模优先级比栈外优先级大1，例如当2+3-5时我们往往从左到右计算，即先算+再算-，使用中缀表达式两个栈计算就是栈外-优先级低于栈顶+，故会弹出+运算符和两个操作数进行计算。

中缀表达式计算（需要两个栈）

• 需要使用两个栈，一个数字栈，用来存数字，另一个是运算符栈，用于存运算符
• 数字栈出栈：只有运算符栈中右运算符出栈时，数字才会弹出两个操作数
• 运算符栈出栈：比较新运算符与栈顶运算符优先级高低，当新运算符优先级高于站顶运算符时，新运算符入栈。当新运算符优先级低于栈顶元素时，栈顶运算符出栈（数字栈弹出两个操作数，计算结果入数字栈），然后再和新的栈顶元素进行比较，直到优先级高于栈顶元素或优先级相等（即栈内左括号，栈外右括号）
• 计算：当数字栈弹出两个操作数，运算符栈出栈运算符时计算，计算结果重新入数字栈

以A+B×(C-D)-E/F为例

1. 一开始数字栈和符为空，数字栈进了A和B，符号栈进了+
2. ×运算符优先级高于＋，进栈
3. ( 优先级在入栈前是最高的(入栈后优先级变为最低)，当然高于×，进栈
4. - 优先级高于站内( ,入栈，D入栈
5. 栈外 ) 优先级低于 - ，- 出栈，计算C-D设为r1，让r1入栈，继续比较，栈外）优先级等于栈内（，把（ 扔掉，出栈结束
6. 后续步骤如图：
   

后缀表达式计算（需要一个栈）

中缀表达式转后缀表达式