浅谈表达式的求值（Vol.1 后缀表达式）
tiger2005
·
2019-04-20 21:43:08
·
算法·理论
0:序言
我们在做一些题目的时候，需要求一些恶心的表达式的值。那么，我们需要用一些快一些的方法求值。
我们能最先想到的就是暴力求值，也就是：
一步步将可运算的地方运算好，最后剩下的就是表达式的值了。
举个栗子：
(6+2*3)/4-5
=(6+6)/4-5
=(12)/4-5
=3-5
=-2
但是，这种方法很容易被卡掉。例如，1+(2+(3+(4+(5+6))))这个式子中，每一次可以执行的符号只有最里面括号的值（因为其他运算符都因为右边的运算没有结果而不能被运算）
这个时候时间复杂度降到了O(n^2)，非常慢。
这个时候，我们就要想一些更快的方法。
1:表达式的树
实际上，我们可以将整个表达式看成一个二叉树，每个非叶子节点上表示的是一个运算符，左右为这个运算符在原来的表达式中左右的值。叶子节点表示的是一个值。
在计算时，我们可以用DFS的方法，在一个节点处先搜索左右儿子代表的值，之后计算。
伪代码如下：
f() 参数：一个整数。返回值：一个整数。
f(now)
if(now是叶子节点) return 这个叶子节点代表的值
return f(左儿子)[now所代表的运算符]f(右儿子)
我们还可以这么看：
很多个数排在一起。每一次，两个相邻的数通过某种方式（就是根代表的运算符）合并成一个数，最后只剩下一个数，这就是表达式的值。
举个例子：
(6+2*3)/4-5
合并过程长这样：
6 2 3 4 5
6 6 4 5
12 4 5
3 5
-2
过程如下：
我们通过以下方式处理字符串（又是伪代码）：
tr() 参数：字符串S 返回：一棵树
tr(S)
if(S只包含一个数字)
return 以这个数字为根的树（只有一个节点）
找到最后运行的运算符X
将X设为这个树的根
将左儿子设为tr(S以X为分界线分开的左边部分)
右儿子设为tr(S以X为分界线分开的右边部分)
return 这个树
最后运行的运算符很好找，只要找这个表达式最外层的运算符中优先级最小的就好（不会优先级的出门左转）
有多个只用取其中一个，这只会影响计算的先后，不影响结果。
很棒。所以我们找到了另一个求表达式值的方法——
转换为树的时候，通过回溯计算值。
但是，很可惜。这个方法中，我们每一次构造的时候，要扫一次字符串并取出一个计算符。还是能用1+(2+(3+(4+(5+6))))这个例子卡成O(n^2)。
那怎么办？
2:表达式的变形
我们想到，一个树有它的三种遍历方式：[前|中|后]序遍历
我们把刚才这个树遍历：
前：- / + 6 * 2 3 4 5
中：6 + 2 * 3 / 4 - 5
后：6 2 3 * + 4 / 5 -
中序遍历就是原式， 但是 我们通过运算优先级建树，这时候受到括号的影响，计算的优先级会改变（括号里面的优先）。
判断的方式很简单。
就比如除号，它在树中左边是加号，运算符优先级比它小，但是竟然先被计算，所以，加号所在子树左右应该加上括号。
我们盯着[前|后]序遍历看。
前序的时候，假设有一个排列如下：
计算符 数字1 数字2
那么这三个数可以被数字1[计算符]数字2代替（就是一次计算）
后序的时候，假设有一个排列如下：
数字1 数字2 计算符
那么这三个数可以被数字1[计算符]数字2代替（就是一次计算）
这个性质由前后序遍历中根不在左右子树中间而来。
由于后序遍历的结果可以用for或in range计算（利用栈即可），我们用后序遍历的结果计算。
P.S. :表达式的[前|中|后]序遍历有对应的名字：前缀表达式（波兰表达式），中缀表达式，后缀表达式（逆波兰表达式）
3:求后缀表达式的简便方法
我们旨在用O(n)的时间求出表达式的值，所以我们只能遍历表达式常数次。
我们先抓住1*2+3这个栗子看，后缀表达式为1 2 * 3 +
我们再抓住1+2*3这个栗子看，后缀表达式为1 2 3 * +
我们从左往右遍历这个式子，我们发现，这两个式子中，
在遍历到第二个运算符的时候，两者的操作不一样——一个将*加入后缀表达式，一个不是。
这仅仅是*和+的优先级有差异。
所以，我们实际上就是要维护一个运算优先级非降的运算符序列，在添加运算符的时候，我们仅仅需要在这个序列中去掉后面的元素，让这个序列添加这个运算符的时候依然有序。
当你维护一个单调的序列的时候，你能想到什么？
单调栈！
我们可以想到，当扫到一个数字的时候，直接加到后缀表达式里面，扫到一个运算符的时候，就把它丢到一个单调栈里面，并且这个单调栈维护的是运算优先级非降的一个字符列表。
也就是说：
* s[N],ret[N];
stack
for i from 1 to N
if(s[i]是一个数) 直接加到ret中
else
while(pri顶部字符的优先级大于s[i]的优先级)
把pri顶端的字符加到ret里面，之后从pri里面弹出
把s[i]加到pri里面
while(pri里面还有字符)
把pri顶端的字符加到ret里面，之后从pri里面弹出
ret -> 后缀表达式
好了，我们已经处理完了不含括号的时候后缀表达式的计算。
那么，当表达式有了括号的时候，怎么办呢？
我们想到，括号里面的计算符的计算优先级比外面的高，所以我们可以这样处理：
碰到(时，直接加入到栈（不进行任何弹出操作），并设置(的优先级为负无穷（这样能保证(不被弹出）
碰到)时，从pri疯狂弹出字符，直到碰到(，把(弹出
为什么要疯狂弹出呢？
很简单，我们要计算完括号里面的计算才能往下走，所以我们需要把括号里面的计算符先弹出，在后缀表达式的计算中相当于计算完括号里面的值。
所以，真正的后缀表达式的寻找方法应该是这样
* s[N],ret[N];
stack
for i from 1 to N
if(s[i]是一个数) 直接加到ret中
else if(s[i]是'(') 直接加到pri中
else if(s[i]是')')
while(pri顶部字符不是'(')
把pri顶端的字符加到ret里面，之后从pri里面弹出
从pri里面弹出'('
else
while(pri顶部字符的优先级大于s[i]的优先级)
把pri顶端的字符加到ret里面，之后从pri里面弹出
把s[i]加到pri里面
while(pri里面还有字符)
把pri顶端的字符加到ret里面，之后从pri里面弹出
ret -> 后缀表达式
模拟(6+2*3)/4-5的计算
扫到(：直接弹入pri。
---
ret :
pri : (
---
扫到6：直接加入ret。
---
ret : 6
pri : (
---
扫到+：加入到pri，因为(的优先级更小，所以没有弹出。
---
ret : 6
pri : ( +
---
扫到2：直接加入ret。
---
ret : 6 2
pri : ( +
---
扫到*：加入到pri，因为+的优先级更小，所以没有弹出。
---
ret : 6 2
pri : ( + *
---
扫到3：直接加入到ret。
---
ret : 6 2 3
pri : ( + *
---
扫到)：将pri中的字符疯狂弹出，直到碰到(，将(弹出。
---
ret : 6 2 3 * +
pri :
---
扫到/：直接加入到pri（pri是空的）。
---
ret : 6 2 3 * +
pri : /
---
扫到4：直接加到ret。
---
ret : 6 2 3 * + 4
pri : /
---
扫到-：加入到pri，因为/的优先级更大，将/弹出并加入到ret。
---
ret : 6 2 3 * + 4 /
pri : -
---
扫到5：直接加入到ret。
---
ret : 6 2 3 * + 4 / 5
pri : -
---
清空pri
ret : 6 2 3 * + 4 / 5 -
因为计算的过程比较简单，所以我相信模拟可以让你们明白。
模拟计算过程：
扫到6，加入栈
+------------
| 6| | | |
+------------
扫到2，加入栈
+------------
| 6| 2| | |
+------------
扫到3，加入栈
+------------
| 6| 2| 3| |
+------------
扫到*，计算2*3，返回6，把6加入栈中
+------------
| 6| 6| | |
+------------
扫到+，计算6+6，返回12，把12加入栈中
+------------
|12| | | |
+------------
扫到4，加入栈
+------------
|12| 4| | |
+------------
扫到/，计算12/4，返回3，把3加入栈中
+------------
| 3| | | |
+------------
扫到5，加入栈
+------------
| 3| 5| | |
+------------
扫到-，计算3-5，返回-2，把-2加入栈中
+------------
|-2| | | |
+------------
结束，返回-2
所以，表达式的计算成功降到了O(n)
4:例题
P1175 表达式的转换
注意 ： 这道题中，pri维护的是升序（不能等于），每次运算需要找到第一个字符并计算。
#include
#include
#include
#include
#include
using namespace std;
//8 - 18行均为运算符的优先级比较
int ope(char q){
if(q=='(') return -1;
if(q=='+') return 0;
if(q=='-') return 0;
if(q=='*') return 1;
if(q=='/') return 1;
if(q=='^') return 2;
return -2/*default*/;
}
bool cmp(char a,char b){
return ope(a)>=ope(b);
}
struct Node{
bool is_num; //是否为运算符
int nm; //数字
char op; //运算符
Node(bool is_num=false,int nm=0,char op='\0'):is_num(is_num),nm(nm),op(op){}
}ret[105]; //后缀表达式
stack
int N; //后缀表达式长度
char A[105];
void print(){
for(int i=0;i if(ret[i].is_num) printf("%d ",ret[i].nm); else printf("%c ",ret[i].op); } printf("\n"); } void solve(){ for(int i=0;A[i];i++){ if(A[i]>='0' && A[i]<='9') ret[N++]=Node(true,A[i]-'0','\0'); else if(A[i]=='(') pri.push(A[i]); else if(A[i]==')'){ while(pri.top()!='('){ //如果保证表达式没有毛病，那么一个)一定对应一个( ，此时不用加!pri.empty() ret[N++]=Node(false,0,pri.top()); pri.pop(); } pri.pop(); } else{ while(!pri.empty() && cmp(pri.top(),A[i])){ //这里要加!pri.empty()，因为有时候在疯狂弹出的时候到头了（栗子中的/和-） ret[N++]=Node(false,0,pri.top()); pri.pop(); } pri.push(A[i]); } } while(!pri.empty()){ ret[N++]=Node(false,0,pri.top()); pri.pop(); } print(); while(N!=1){ //找到第一个计算符 int l=0; while(ret[l].is_num) ++l; //暴力计算 switch(ret[l].op){ case '+': ret[l-2]=Node(true,ret[l-2].nm+ret[l-1].nm,'\0'); break; case '-': ret[l-2]=Node(true,ret[l-2].nm-ret[l-1].nm,'\0'); break; case '*': ret[l-2]=Node(true,ret[l-2].nm*ret[l-1].nm,'\0'); break; case '/': ret[l-2]=Node(true,ret[l-2].nm/ret[l-1].nm,'\0'); break; case '^': ret[l-2]=Node(true,pow(ret[l-2].nm,ret[l-1].nm),'\0'); break; default: break; } //往左挪两格 for(int i=l-1;i print(); N-=2; } } int main(){ scanf("%s",A); solve(); } 提交记录 5:In the end 表达式的求值在一些大模拟题目中很常见（比如说未来程序·改中的语句）。当然，在平常编写科学计算器的时候也是一个重要的知识点。 所以，后缀表达式在表达式求值的题中节省了时间（O(n^2) \rightarrow O(n)）。 完结撒花！*★,°*:.☆(￣▽￣)/$:*.°★* 。 放心吧，我不会推荐未来程序·改的 最后，感谢@xhhkwy 给出单调栈的修改。 P.S. : 本文旨在让大家更了解后缀表达式的运行方式和正确原因，而不是死记硬背的代码，所以那些觉得知识点简单的也不要狂喷。