LeetCode 150. 逆波兰表达式求值

1. 逆波兰表达式求值

难度 中等 OJ链接

逆波兰表达式是什么呢？可能大家不是很理解，我们来看一下：
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

逆波兰表达式主要有以下两点优点：
1.去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
2.适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。

其实这道题的意思是：后缀表达式，我们该如何去运算？
解题思路：

第一步：遇到操作数，入栈

第二步：遇到操作符，则取出栈顶两个数字进行计算，并将结果压入栈中

我们按照这两个步骤来走，然后遇到2，再入栈。

遇到 / 操作符，取栈顶两个数计算，然后将结果入栈。

遇到 + 操作符，取栈顶两个数计算，然后将结果入栈。

遇到5，入栈。

遇到 - ，取栈顶两个数计算，然后将结果入栈。

这就是后缀表达式的计算方法。

代码实现：

如果是操作数，我们就入栈。但我们需要将字符串转换为整数，这里我们可以用stoi函数。

此时，我们取到栈顶的两个数了，现在需要进行运算。但是我们不知道是那个操作符，所以这里可以使用switch语句。

最后，栈里只剩下最后一个数，我们返回。

但是这里出现了一个错误。

这里有一个相乘超出范围了。这个数大于int最大范围2^31-1。最后乘以-1后的值是合法的，但是倒数第二步的值是非法的。我们可以换成long类型,long在Leetcode里是8个字节。

这样相乘就是合法的。

C++11用包装器实现：

2. 如何将中缀表达式变成后缀表达式

第一步：遇到操作数，存储
第一个是1，我们将1存储起来。

第二步：遇到运算符，有三个情况：
a.栈为空，入栈

然后2是操作数，我们把它存储起来。然后遇到乘号。
b.和栈顶运算符比较，如果比栈顶优先级高，入栈

遇到3操作数，存储起来。然后遇到除号。
c.和栈顶运算符比较，比栈顶优先级低或者一样，出栈顶运算符，然后再和栈顶运算符比较，去执行b和c情况

所以，再次比较时，除号比加号的优先级高，除号入栈。

然后是操作数2，我们把它存储起来。后面是-号，比除号优先级小，出栈。

再和栈顶运算符比较，-号和+号的优先级一样，出栈。

此时栈为空，入栈。

然后是操作数5，存储起来。当结束时，栈里的运算符全部出栈。