逆波兰表达式求值【中等】

题目

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

有效的算符为 '+'、'-'、'*' 和 '/' 。
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
两个整数之间的除法总是 向零截断 。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位 整数表示。

示例 1：

输入：tokens = ["2","1","+","3",""]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) 3) = 9
示例 2：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：

输入：tokens = ["10","6","9","3","+","-11","","/","","17","+","5","+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
((10 (6 / ((9 + 3) -11))) + 17) + 5
= ((10 (6 / (12 -11))) + 17) + 5
= ((10 (6 / -132)) + 17) + 5
= ((10 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

思路

逆波兰表达式的操作步骤

1、从左到右遍历逆波兰表达式，进行如下操作：

2、如果遇到操作数，则将操作数入栈；

3、如果遇到运算符，则将两个操作数出栈，其中先出栈的是右操作数，后出栈的是左操作数，使用运算符对两个操作数进行运算，将运算得到的新操作数入栈。

4、整个逆波兰表达式遍历完毕之后，栈内只有一个元素，该元素即为逆波兰表达式的值。

5、我们这里简单说就是把每个值取出，如果是遇到运算符，就取两个数字出来，然后再把这个结果放入到栈中。以此类推

6、如果不是运算符就是数字，我们把数字放入到栈中就行。经过一系列循环就可以知道，栈中最后剩下那个就是结果

代码实现【java】

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack();
        for(String s:tokens){
            if("+".equals(s)){
                // 这里多了个正负号的原因是为了避免+-错误
                stack.push(-stack.pop()+stack.pop());
            }else if("-".equals(s)){
                stack.push(-stack.pop()+stack.pop());
            }else if("*".equals(s)){
                stack.push(stack.pop()*stack.pop());
            }else if("/".equals(s)){
                // 这边除法需要注意一下，设置两个变量，否则容易报错/zero
                int num1 = stack.pop();
                int num2 = stack.pop();
                stack.push(num1/num2);
            }else{
                // 如果都不满足，我们就把字符串数字，转换成int类型的数字存入到栈中
                stack.push(Integer.valueOf(s));
            }
        }
        // 最后把结果返回就行,此时栈中就只有一个数字，就是答案
        return stack.pop();
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/evaluate-reverse-polish-notation/solutions/667892/ni-bo-lan-biao-da-shi-qiu-zhi-by-leetcod-wue9/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。