栈的应用---后缀表达式的计算

步骤一：中缀表达式转后缀表达式

①设立一个操作符栈，用以临时存放操作符；设立一个数组或队列，用以存放后缀表达式。

②从左到右扫描中缀表达式，如果遇到操作数就直接把它们加入到后缀表达式中。

③如果碰到操作符op，就将其优先级与操作符栈的栈顶操作符的优先级比较

· 若op的优先级高于栈顶操作符的优先级，则压入操作符栈。

· 若op的优先级低于或等于栈顶操作符的优先级，则将操作符栈的操作符不断弹出到后缀表达式中，直到op的优先级高于栈顶操作符的优先级

④重复上述操作，直到中缀表达式扫描完毕，之后若操作符栈中仍有元素，则将它们依次弹出至后缀表达式中。

操作符的优先级：乘法==除法>加法==减法，在具体实现上可以用map建立操作符和优先级的映射。

步骤二：计算后缀表达式

从左到右扫描后缀表达式，如果是操作数，就压入栈；如果是操作符，就连续弹出两个操作数（注意：后弹出的是第一操作数，先弹出的是第二操作数），然后进行操作符的操作，生成的新操作数压入栈中。当栈中就存在一个数时，就是最终的答案。

· 注意除法可能导致浮点数，因此操作数类型要设成浮点型。

代码见胡凡算法笔记 P249