算法

之前在字节面试的时候，面试官给我出了一道算法题：给定一个用字符串表示的算式，算式中只有+， -， *， /，请计算出最终结果。 比如 2+3*4-2/2。 很明显，如果没有 * 和 / ，那我们直接一个循环处理即可，但是有了 * 和 /，算式就有了优先级，我们需要先计算优先级高的，在计算优先级低的。 面试官提醒我可以使用栈来处理，我才恍然大悟，然后迅速用代码实现。 面试结束后，我就去细了解了一下这类问题的做法，这种字符串公式的表达叫做：中缀表达式，与之类似的还有前缀表达式和后缀表达式，前缀表达式和后缀表达式又被叫做波兰表达式和逆波兰表达式。 中缀表达式 其实很多读者在数据结构这一门课上，就已经学过中缀表达式了，但是对于我这个非科班的来说，第一次接触还是非常新鲜的，对于学过的朋友权当复习了。 使用栈这种数据结构，可以很好的处理仅有加减乘除四种运算符（不含括号）的公式。 栈是一种先入后出（FILO）的数据结构，可以将数据入栈和出栈，入栈数据会在栈顶，出栈是将栈顶的数据取出。 对 2+3*4-2/2 表达式来说，我们将数字压入栈，如果遇到 * 和 / 这两个优先级高的操作，我们将栈中的数据出栈，和操作符后面的数据进行 * 和 / 操作之后，将结果入栈，遇到 + 则不做操作，遇到 - 则对后一个数据进行取负，将数据压入栈即可。 就对 2+3*4-2/2 举例子： 1 2 3 4 5 6 7 8 9 10 轮询到第一个数字 2 压入栈中，当前栈 [2] 操作符 +， 抛弃 数字 3 压入栈，当前栈：[2, 3] 操作符 *,将栈顶取出一个值 3，当前栈 [2] 将下一个数字 4 和刚刚取出的值 3 做 * 操作得到 12，压入栈，目前栈：[2, 12] 操作符 -, 对下一个数取负 数字 2，取负后压入栈，目前栈 [2, 12, -2] 操作符 /, 取出栈顶值 -2,目前栈 [2, 12] 将下一个数字 2 和刚刚取出的值 -2 做 / 操作得到 1,压入栈，目前栈 [2, 12, -1] 最后对栈里的数据进行相加，得到 2+12-1 = 13 13 即是最终值。 因为 golang 中没有现成的栈 api，我们需要用队列来手动实现一个。 实现代码如下：...