拜托，面试别再问我表达式求值了！！！

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

题目大概是这样的：

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

输出表达式的值，即：63

我暗示的问：应该用什么数据结构？

候选人回答：栈。

画外音：算是答对。

问：时间复杂度呢？

回答：O(n^2)

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

我接着提示：应该先计算哪一步？

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

画外音：额，难道是乘除大于加减？

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

怎么用栈来实现呢？

候选人：…

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

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

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

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

（1）双栈，一个操作数栈，一个运算符栈；

（2）运算符优先级，栈顶运算符，和，即将入栈的运算符的优先