表达式求值,有些候选人总以为自己懂了!
上周面试一个候选人，问了一个数据结构与算法的问题，表达式求值。
题目大概是这样的：
输入
长度为n的字符串，例如：
1+2+3*4*5
输出
表达式的值，即：
63
我暗示的问：
应该用什么数据结构？
候选人回答：
栈。
画外音：
算是答对。
问：
时间复杂度呢？
回答：
O(n^2)
画外音：
额，应该不需要两个for循环吧。
我接着提示：
应该先计算哪一步？
候选人回答：
先计算3*4。
画外音：
额，难道是乘除大于加减？
实际应该先计算1+2，说明候选人对“表达式求值”并没有搞透。
怎么用栈来实现呢？
候选人：
…
本来以为是送分题，候选人竟一时语塞。
为了广大面试的同学不再在这一题上送命，今天花几分钟把这个问题讲透彻。
画外音：
希望没有帮面试官增加题库。
“表达式求值”问题，两个核心关键点：
（1）双栈，一个操作数栈，一个运算符栈；
（2）运算符优先级，
栈顶运算符
，和，
即将入栈的运算符
的优先级比较：
这里的含义是：
（1）如果栈顶是+，即将入栈的是+，栈顶优先级高，需要先计算，再入栈；
（2）如果栈顶是+，即将入栈的是*，栈顶优先级低，直接入栈；
（3）如果栈顶是*，即将入栈的是+，栈顶优先级高，需要先计算，再入栈；
（4）如果栈顶是*，即将入栈的是*，栈顶优先级高，需要先计算，再入栈；
画外音：
运算符有+-*/()~^&都没问题，如果共有n个运算符，会有一个n*n的优先级表。
有了运算符表，一切就好办了。
一开始，
初始化
好输入的字符串，以及操作数栈，运算符栈。
一步步，扫描字符串，操作数一个个入栈，运算符也入栈。
画外音：
如果有“789”这样的多个字符的多位数，要先转化为数字789，这个过程很容易。
下一个操作符要入栈时，需要先比较优先级。
栈内的优先级高，必须
先计算，才能入栈
。
计算的过程为：
（1）操作数出栈，作为num2；
（2）操作数出栈，作为num1；
（3）运算符出栈，作为op；
（4）计算出结果；
（5）结果入操作数栈；
接下来，运算符和操作数才能继续入栈。
下一个操作符要入栈时，继续比较与栈顶的优先级。
栈内的优先级低，可以直接入栈
。
字符串继续移动。
又要比较优先级了。
栈内的优先级高，还是
先计算
（3*4=12）
，再入栈
。
不断入栈，直到字符串扫描完毕。
不断出栈，直到得到最终结果3+60=63，算法完成。
总结
“表达式求值”问题，两个核心关键点：
（1）双栈，一个
操作数栈
，一个
运算符栈
；
（2）运算符优先级，栈顶运算符，和，即将入栈的运算符的优先级比较：
相关文章： 《线上问题排查，这些命令你一定用得到！》 《顶尖的人都是怎么想的！（很残酷）》
- 如果栈顶的运算符优先级低， 新运算符直接入栈
- 如果栈顶的运算符优先级高， 先出栈计算，新运算符再入栈
这里的含义是：
（1）如果栈顶是+，即将入栈的是+，栈顶优先级高，需要先计算，再入栈；
（2）如果栈顶是+，即将入栈的是*，栈顶优先级低，直接入栈；
（3）如果栈顶是*，即将入栈的是+，栈顶优先级高，需要先计算，再入栈；
（4）如果栈顶是*，即将入栈的是*，栈顶优先级高，需要先计算，再入栈；
画外音：
运算符有+-*/()~^&都没问题，如果共有n个运算符，会有一个n*n的优先级表。
有了运算符表，一切就好办了。
一开始，
初始化
好输入的字符串，以及操作数栈，运算符栈。
一步步，扫描字符串，操作数一个个入栈，运算符也入栈。
画外音：
如果有“789”这样的多个字符的多位数，要先转化为数字789，这个过程很容易。
下一个操作符要入栈时，需要先比较优先级。
栈内的优先级高，必须
先计算，才能入栈
。
计算的过程为：
（1）操作数出栈，作为num2；
（2）操作数出栈，作为num1；
（3）运算符出栈，作为op；
（4）计算出结果；
（5）结果入操作数栈；
接下来，运算符和操作数才能继续入栈。
下一个操作符要入栈时，继续比较与栈顶的优先级。
栈内的优先级低，可以直接入栈
。
字符串继续移动。
又要比较优先级了。
栈内的优先级高，还是
先计算
（3*4=12）
，再入栈
。
不断入栈，直到字符串扫描完毕。
不断出栈，直到得到最终结果3+60=63，算法完成。
总结
“表达式求值”问题，两个核心关键点：
（1）双栈，一个
操作数栈
，一个
运算符栈
；
（2）运算符优先级，栈顶运算符，和，即将入栈的运算符的优先级比较：
- 如果栈顶的运算符优先级低，新运算符 直接入栈
- 如果栈顶的运算符优先级高， 先出栈计算 ，新运算符 再入栈
相关文章： 《线上问题排查，这些命令你一定用得到！》 《顶尖的人都是怎么想的！（很残酷）》
评论