拜托,面试别再问我表达式求值了!!!

  1. 云栖社区>
  2. 阿里云MVP>
  3. 博客>
  4. 正文

拜托,面试别再问我表达式求值了!!!

初商 2019-08-07 23:56:34 浏览337
展开阅读全文

前段时间面试一个候选人,问了一个数据结构与算法的问题,表达式求值。

题目大概是这样的:

输入长度为n的字符串,例如:1+2+345

输出表达式的值,即:63

我暗示的问:应该用什么数据结构?

候选人回答:栈。

画外音:算是答对。

问:时间复杂度呢?

回答:O(n^2)

画外音:额,应该不需要两个for循环吧。

我接着提示:应该先计算哪一步?

候选人回答:先计算3*4。

画外音:额,难道是乘除大于加减?

实际应该先计算1+2,说明候选人对“表达式求值”并没有搞透。

怎么用栈来实现呢?

候选人:…

本来以为是送分题,候选人竟一时语塞。

为了广大面试的同学不再在这一题上送命,今天花几分钟把这个问题讲透彻。

画外音:希望没有帮面试官增加题库。

“表达式求值”问题,两个核心关键点:

(1)双栈,一个操作数栈,一个运算符栈;

(2)运算符优先级,栈顶运算符,和,即将入栈的运算符的优先

网友评论

登录后评论
0/500
评论
初商
+ 关注
所属云栖号: 阿里云MVP