上周面试了一个候选人，问了一个数据结构与算法，表达式求值的问题。题目大概是这样的：输入一个长度为n的字符串，比如：1+2+3*4*5输出表达式的值，即：63我在题中暗示了：应该用什么数据结构？考生答案：堆栈。画外音：没错。Q：时间复杂度呢？答案：O(n^2)画外音：嗯，应该不需要两个for循环。然后提示：先计算哪一步？候选答案：先计算3*4。画外音：嗯，乘除比加减大吗？其实应该先计算1+2，说明考生对“表情评价”没有吃透。如何使用栈来实现呢？考生：……本来以为是分题，结果考生一时语塞。为了让大部分面试的同学不再死在这个问题上，我今天就花几分钟把这个问题解释清楚。画外音：希望我没有帮面试官增加题库。“表达式求值”问题，两个核心关键点：（1）双栈，一个操作数栈，一个操作符栈；(2)运算符优先级，栈顶运算符，和，即将入栈的运算符优先级比较：如果栈顶运算符的优先级低，则新运算符直接压入栈中。如果栈顶运算符的优先级高，则先进行计算，然后将新的运算符压入栈中。还是在1+以2+3*4*5为例，看看如何利用上面的两个关键点来实现计算。首先，这个例子只有+和*两个运算符，所以它的运算符表是：这里的意思是：如果栈顶是+，那么即将入栈的是+，栈顶优先级高，需要先计算，然后入栈；若栈顶为+，则入栈对象为*，栈顶优先级低，直接入栈；如果栈顶是*，则要入栈的对象是+，栈顶的优先级高，需要先计算，然后入栈；如果栈顶是*，则入栈的是*，栈顶的优先级高，需要先计算，再入栈；画外音：包括+-*/()~^&在内的运算符都没有问题，如果有n个运算符，就会有n*n个优先级表。有了操作台，一切都好办。首先，初始化输入字符串，以及操作数栈和运算符栈。一步步扫描字符串，将操作数一个一个压栈，运算符也压栈。画外音：如“789”等多个字符有多个数字，必须先转换为数字789。这个过程非常简单。当下一个算子要入栈时，需要先比较优先级。在栈中的优先级很高，必须经过计算才能入栈。计算过程为：操作数出栈为num2；操作数作为num1从堆栈中弹出；运算符作为op从堆栈中弹出；计算结果；(5)结果放入操作数栈；接下来，运算符和操作数依次压入栈中。当下一个算子要入栈时，继续和栈顶比较优先级。栈中优先级低，可以直接入栈。绳子继续移动。是时候比较优先级了。栈中优先级高，所以先计算（3*4=12）再入栈。继续推入堆栈，直到字符串被扫描。不断出栈，直到得到最终结果3+60=63，算法完成。总结一下“表达式求值”的问题，两个核心关键点：（1）双栈，一个操作数栈，一个操作符栈；(2)运算符优先级，栈顶运算符，and,将入栈运算符优先级比较：如果栈顶运算符优先级低，则新的运算符直接入栈如果栈顶的运算符优先级高，则先计算，然后将新的运算符入栈这种方法时间复杂度为O(n)，整个字符串只需要被扫描一次。想法比结论更重要，你学会了吗？
