表达式求值,有些候选人总以为自己懂了!-技术圈

上周面试一个候选人，问了一个数据结构与算法的问题，表达式求值。

题目大概是这样的：

输入

长度为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的优先级表。

有了运算符表，一切就好办了。