聚合国内IT技术精华文章,分享IT技术精华,帮助IT从业人士成长
IT技术精华
设为首页
加入收藏
订阅本站
IT技术文章精选
2024
每日Shell
关于
热门搜索:
IT技术
Linux
系统
算法
架构
数据库
优化
python
分布式
php
您的位置:
首页
» 技术文章 » 正文
表达式求值,有些候选人总以为自己懂了!
2022-11-23 23:49
浏览: 2278967 次
我要评论
(0 条)
字号:
大
中
小
#算法
18
个
#面试
14
个
#架构师
18
个
#互联网
53
个
上周面试一个候选人,问了一个数据结构与算法的问题,
表达式求值
。
题目大概是这样的:
输入
长度为n的字符串,例如:
1+2+3*4*5
输出
表达式的值,即:
63
我暗示的问:
应该用什么数据结构?
候选人回答:
栈。
画外音:
算是答对。
问:
时间复杂度呢?
回答:
O(n^2)
画外音:
额,应该不需要两个for循环吧。
我接着提示:
应该先计算哪一步?
候选人回答:
先计算3*4。
画外音:
额,难道是乘除大于加减?
实际应该先计算1+2,说明候选人对“表达式求值”并没有搞透。
怎么用栈来实现呢?
候选人:
…
本来以为是送分题,候选人竟一时语塞。
为了广大面试的同学不再在这一题上送命,今天花几分钟把这个问题讲透彻。
画外音:
希望没有帮面试官增加题库。
“表达式求值”问题,两个核心关键点:
(1)
双栈
,一个操作数栈,一个运算符栈;
(2)
运算符优先级
,
栈顶运算符
,和,
即将入栈的运算符
的优先级比较:
如果栈顶的运算符
优先级低
,
新运算符直接入栈
如果栈顶的运算符
优先级高
,
先出栈计算,新运算符再入栈
仍以1+2+3*4*5举例,看是如何利用上述两个关键点实施计算的。
首先,这个例子只有+和*两个运算符,所以它的运算符表是:
这里的含义是:
(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)
运算符优先级
,栈顶运算符,和,即将入栈的运算符的优先级比较:
如果栈顶的运算符
优先级低
,新运算符
直接入栈
如果栈顶的运算符
优先级高
,
先出栈计算
,新运算符
再入栈
这个方法的
时间复杂度为O(n)
,整个字符串只需要扫描一遍。
思路
比结论重要,学到了吗?
架构师之路
-分享技术
思路
相关文章:
《
线上问题排查,这些命令你一定用得到!
》
《
顶尖的人都是怎么想的!(很残酷)
》
预览时标签不可点
标签:
知识来源:
mp.weixin.qq.com/s/?source_url=https%3A%2F%2Fmp.weixin.qq.com%2Fs%2F5zlLpHDkoDEh9FwBG2aj6Q&id=42ef4e424aec371ad402482fb11b921f
本文链接:
表达式求值,有些候选人总以为自己懂了!
打印
复制链接
上一篇:
Meta否认扎克伯格明年辞任CEO;著名黑客成推特实习生;Windows 8.1明年1月10日停止支持|极客头条
下一篇:
线上系统的JVM停顿几十秒,我们两个月才排查出真凶!
网友评论
已有
0
条评论,
我也要评论
发表评论
用户名:
*
电子邮箱:
*
(保密)
网站网址:
验证码:
申请头像
添加评论内容
Ctrl+Enter 快捷回复
每天为热爱学习的工程师/架构师/技术经理/CTO更新最新最优质的IT技术精华文章,帮助你突破年薪百/千万。
➨GitHub:
https://github.com/taogogo
➨关注微博:
http://weibo.com/taogogo
随机推荐
Paradigm CTF 2021 比赛环境
你真的了解微服务吗?
伴鱼机器学习预测服务:设计篇
企业快速创新的基石——用友 BIP | iuap云平台
一个数据库事务 Bug 引发的惨剧
腾讯看点CTO徐羽: QQ浏览器背后的推荐AI中台 | AICon
美团商品知识图谱的构建及应用
Writeup | Paradigm CTF 2021 Part 1
假如让你来设计数据库中间件
标签云
IT技术
Linux
系统
算法
架构
数据库
优化
python
分布式
php
App
opensource
面试
大数据
数据
术→技巧
java
教程
Web开发
Linux & Unix
Technical
程序设计
原创
机器学习
技术
docker
SQL Server
Javascript
Cache
程序开发
nginx
Working case
默认分类
..experience
编程
oracle
安全
杂项
Redis
操作系统
网友评论已有0条评论, 我也要评论