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