表达式求值

表达式求值是一个很经典的问题，输入一个形如“(3+2)*5*7+3”的字符串，要求输出它的结果。
对于这个问题，有很多种处理方法。用计算器显然是个不错的方法，不过，这不在讨论范围内。

一个最朴素的方法：递归+分治。
定义一个函数solve(int i,int j)，表示求出str[i]~str[j]这部分字串的值。
如果这个字串不含符号，那么返回它对应的数字。
如果它两端是一对括号，那么，返回solve(i + 1,j - 1)
如果它其中有加号,加号的位置在k，那么返回solve(i,k - 1)+solve(k + 1,j)，减号也做类似处理。
如果有乘号在k位置，则返回solve(i,k - 1) * solve(k + 1,j)，除号也类似。
这个方法的正确性是显而易见的，在处理小规模数据上速度也很快，不过，由于要多次扫描字符串，这个算法的效率还是比较低下的。

在介绍比较先进的算法前，要先说明几个概念问题。我们平时用的表达式叫做“中序表达式”，以“(3+2)*5*7+3”为例，如果把数字作为叶子节点，操作符作为内部节点，它可以构成一个二叉树。

中序表达式有一个很糟糕的地方就是它需要括号，上面的算法实际上就是不断求出各个子树的值，进而得到整个树的值。

这个树的后序遍历是：3 2+5×7×3+
由于运算符在操作数的后面，故起名为后序表达式，也叫逆波兰表达式。

与中序表达式相比，后序表达式的优点就是不需要括号， 更计算机处理更方便。

顺便提一下，如果要手动把一个中序表达式转换成后序表达式并不需要写出右边那个二叉树，只需要：在保证运算顺序不变的情况下，把所有能加括号的地方都加括号。再把括号内的运算符移动到括号后面，最后除去括号即可。这个方法可以在NOIP初赛时用用。

下面介绍正经的中序转后序的算法：

建立一个空栈S。
从左到右扫描输入的字符串，如果碰到了操作数，则直接输出。如果碰到了运算符，那么分两种情况：

1. 如果栈空或者当前运算符大于栈顶运算符的优先级，那么push
2. 如果当前运算符优先级小于等于栈顶的，那么重复执行pop直到栈顶是‘（’，或者满足1条件。然后push

如果遇到‘（’，直接push
如果遇到‘）’，则不断pop直到pop出‘（’

可以发现，S中存储的是运算符或者括号。

得到了后序表达式，求值就简单多了。

同样，先建立一个空栈S，从前到后读取后缀表达式，如果遇到数字，那么直接push。
如果遇到运算符（假设为#），那么：
a = pop();b = pop();push(a # b);
最后，S中仅存在一个元素，就是表达式的值。