浅谈表达式的求值（Vol.1 后缀表达式）

# 0:序言 > 我们在做一些题目的时候，需要求一些恶心的表达式的值。那么，我们需要用一些快一些的方法求值。 我们能最先想到的就是暴力求值，也就是： 一步步将可运算的地方运算好，最后剩下的就是表达式的值了。 举个栗子： ```cpp (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<char> pri; 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<char> pri; 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 表达式的转换](https://www.luogu.org/problemnew/show/P1175) __注意__ ： 这道题中，pri维护的是升序（不能等于），每次运算需要找到第一个字符并计算。 ```cpp #include<cstdio> #include<cstring> #include<stack> #include<algorithm> #include<cmath> 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<char> pri; int N; //后缀表达式长度 char A[105]; void print(){ for(int i=0;i<N;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<N;i++) ret[i]=ret[i+2]; print(); N-=2; } } int main(){ scanf("%s",A); solve(); } ``` [提交记录](https://www.luogu.org/recordnew/show/18591666) # 5:In the end 表达式的求值在一些大模拟题目中很常见（比如说未来程序·改中的语句）。当然，在平常编写[科学计算器](https://www.luogu.org/paste/tcp9ntag)的时候也是一个重要的知识点。 所以，后缀表达式在表达式求值的题中节省了时间（$O(n^2) \rightarrow O(n)$）。 ## 完结撒花！```*★,°*:.☆(￣▽￣)/$:*.°★* 。``` ~~放心吧，我不会推荐未来程序·改的~~ 最后，感谢@xhhkwy 给出单调栈的修改。 P.S. : 本文旨在让大家更了解后缀表达式的运行方式和正确原因，而不是死记硬背的代码，所以那些觉得知识点简单的也不要狂喷。