1 中缀表达式转后缀表达式

1.1 宏观思路

去掉所有符号，根据运算顺序添加运算符

1.2 微观实现

定义\(\#%\)等级为0（自定义），\(+\)等级为1，\(\times\)等级为2（其他种类运算符同理）

\(\#%\)入栈，在中缀表达式后加\(\#\)（注：栈维护运算符本身和其优先级的二元组，保持二元组的第二项从栈底到栈顶单调递增，遇到和栈顶同样的运算符都要弹出）

指针从左到右扫描中缀表达式，遇到数字直接输出，遇到运算符就将运算符和其原本优先级等级+\(f\)（见下）入栈。（一定注意要维护栈的单调性，出栈的运算符直接输出）

维护一个初值为\(0\)整型标记变量\(f\)用于维护括号层数对于运算符优先级等级的贡献，具体地，选取一个大于优先级最高运算符等级的数\(\Delta f\)。（例如在本例中，可以选取\(\Delta f=10\)）遇到左括号将\(f+=\Delta f\)，遇到右括号将\(f-=\Delta f\)，如上所述，让运算符入栈的同时记录原本等级\(+f\)。

指针到底后输出栈顶并弹栈直到栈为空。

时间复杂度\(O(n)。\)

其实我至今都不知道井号的作用是什么。

2 后缀表达式求值

从左到右扫描后缀表达式，遇到数字入栈，遇到运算符询问并弹出栈顶两个元素并计算，将计算结果再次入栈。

扫描到底时栈中唯一元素即为表达式的值。

时间复杂度\(O(n)\)。

原文地址：http://www.cnblogs.com/KimJeonghui/p/16858946.html