表达式求值,有些候选人总以为自己懂了!
架构师之路
共 2386字,需浏览 5分钟
·
2022-11-24 16:33
上周面试一个候选人,问了一个数据结构与算法的问题,表达式求值。
题目大概是这样的:
输入
长度为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)运算符优先级,栈顶运算符,和,即将入栈的运算符的优先级比较:
相关文章: 《线上问题排查,这些命令你一定用得到!》 《顶尖的人都是怎么想的!(很残酷)》
- 如果栈顶的运算符优先级低, 新运算符直接入栈
- 如果栈顶的运算符优先级高, 先出栈计算,新运算符再入栈
![3186f2998038a2b20fdfbdb61f223cdc.webp](https://filescdn.proginn.com/e980c548b918b1b4cdab44599fc35eb4/3186f2998038a2b20fdfbdb61f223cdc.webp)
![502da3a8e4666cf3c47008981f8e3151.webp](https://filescdn.proginn.com/6b493a5f11b3e3c85145a02bb367b992/502da3a8e4666cf3c47008981f8e3151.webp)
![7aaa8dead7d61073b8d9dd04bb8c4a85.webp](https://filescdn.proginn.com/923c7eb6b428343263d9bd62ffa2e758/7aaa8dead7d61073b8d9dd04bb8c4a85.webp)
![5268a2c868f742d7536bf5da30b8342a.webp](https://filescdn.proginn.com/7c824367348a01fed29246885b4b7274/5268a2c868f742d7536bf5da30b8342a.webp)
![afd4de4e2c9476bb167a15448d2d4733.webp](https://filescdn.proginn.com/7b1da2f8cd49bfadea2bb12f41cdab38/afd4de4e2c9476bb167a15448d2d4733.webp)
![29e9d27566fceb142ba2e6421f9d0994.webp](https://filescdn.proginn.com/7e137fa83210c3768cf19583a41f46d2/29e9d27566fceb142ba2e6421f9d0994.webp)
![684c3f37c4e0f3161c05591e04a888cd.webp](https://filescdn.proginn.com/25f7a299da558202f6d7c34fd5d638f5/684c3f37c4e0f3161c05591e04a888cd.webp)
![460c3fe49f6977b45ab60fa5db8abb9b.webp](https://filescdn.proginn.com/7e50285a8355f9cb1dba0f80b4200cce/460c3fe49f6977b45ab60fa5db8abb9b.webp)
![aaebc163eacd650db6049d6b91441b37.webp](https://filescdn.proginn.com/7404caae788f747eb2687d6ca6404a9d/aaebc163eacd650db6049d6b91441b37.webp)
![5bdf6e0b06977f626e68cd9797f4adc7.webp](https://filescdn.proginn.com/3c36696d6578b93e84bd21824eba89ff/5bdf6e0b06977f626e68cd9797f4adc7.webp)
![fc5b5a7522b1e688c520ab12bd0a9a70.webp](https://filescdn.proginn.com/195cea4e3f60a5a4f36bb0a8a0194be3/fc5b5a7522b1e688c520ab12bd0a9a70.webp)
![f7b3a70efd1d4dfdd9189e5e4cad2865.webp](https://filescdn.proginn.com/176bc2d84fa2debc93de4a85aadcc0b6/f7b3a70efd1d4dfdd9189e5e4cad2865.webp)
- 如果栈顶的运算符优先级低,新运算符 直接入栈
- 如果栈顶的运算符优先级高, 先出栈计算 ,新运算符 再入栈
相关文章: 《线上问题排查,这些命令你一定用得到!》 《顶尖的人都是怎么想的!(很残酷)》
评论