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

题目大概是这样的：

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

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

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

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

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

(2)运算符优先级，栈顶运算符，和，即将入栈的运算符的优先级比较：

如果栈顶的运算符优先级低，新运算符直接入栈

如果栈顶的运算符优先级高，先出栈计算，新运算符再入栈

仍以1+2+3*4*5举例，看是如何利用上述两个关键点实施计算的。

首先，这个例子只有+和*两个运算符，所以它的运算符表是：

这里的含义是：

如果栈顶是+，即将入栈的是+，栈顶优先级高，需要先计算，再入栈;

如果栈顶是+，即将入栈的是*，栈顶优先级低，直接入栈;

如果栈顶是*，即将入栈的是+，栈顶优先级高，需要先计算，再入栈;

如果栈顶是*，即将入栈的是*，栈顶优先级高，需要先计算，再入栈;

画外音：运算符有+-*/()~^&都没问题，如果共有n个运算符，会有一个n*n的优先级表。

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

一开始，初始化好输入的字符串，以及操作数栈，运算符栈。

一步步，扫描字符串，操作数一个个入栈，运算符也入栈。

画外音：如果有“789”这样的多个字符的多位数，要先转化为数字789，这个过程很容易。

下一个操作符要入栈时，需要先比较优先级。

栈内的优先级高，必须先计算，才能入栈。

计算的过程为：

操作数出栈，作为num2;

操作数出栈，作为num1;

运算符出栈，作为op;

计算出结果;

结果入操作数栈;

栈内的优先级低，可以直接入栈。

字符串继续移动。

又要比较优先级了。

栈内的优先级高，还是先计算(3*4=12)，再入栈。

不断入栈，直到字符串扫描完毕。

不断出栈，直到得到最终结果3+60=63，算法完成。

总结

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

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

(2)运算符优先级，栈顶运算符，和，即将入栈的运算符的优先级比较：

如果栈顶的运算符优先级低，新运算符直接入栈

如果栈顶的运算符优先级高，先出栈计算，新运算符再入栈

这个方法的时间复杂度为O(n)，整个字符串只需要扫描一遍。

思路比结论重要，学到了吗?

【本文为51CTO专栏作者“58沈剑”原创稿件，转载请联系原作者】

戳这里，看该作者更多好文

【编辑推荐】

深度策略梯度算法是真正的策略梯度算法吗？

除了冒泡排序，你知道Python内建的排序算法吗？

量化评估、算法拓展：强化学习研究的10大原则

机器学习必学10大算法

想伪装成资深程序员？知道这三个数据结构就够了