[数据结构与算法]LeetCode刷题：逆波兰表达式求值

根据逆波兰表示法，求表达式的值。
有效的算符包括 +、-、、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
注意 两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例一：

示例二：

示例三：

1.计算后缀表达式的过程

逆波兰表达式（后缀表达式）求值的过程：
后缀表达式的求值过程是从左到右一次扫描后缀表达式postexp，若读取的是一个操作数，将它压进操作数栈，若读取的是一个运算符op，从操作数栈中连读出栈两个操作数，假设为a（第一个出栈元素）和b（第二个出栈元素），计算b op a的值，并将计算结果压进操作数栈。当整个后缀表达式扫描完毕后，操作数栈中的栈顶元素就是后缀表达式的计算结果。

简单来说：计算逆波兰表达式的值时，使用一个栈存储操作数，从左到右遍历逆波兰表达式，进行如下操作：
如果遇到操作数，则将操作数入栈；
如果遇到运算符，则将两个操作数出栈，其中先出栈的是右操作数，后出栈的是左操作数，使用运算符对两个操作数进行运算，将运算得到的新操作数入栈。
整个逆波兰表达式遍历完毕之后，栈内只有一个元素，该元素即为逆波兰表达式的值。

2.LinkedList作为栈的相关API

另外，解决该问题需要一个栈的数据结构，这里使用LinkedList替代Stack,因为LinkedList实现了Deque结构，因此采用多态的定义方法如下所示：

Deque<Integer> stack=new LinkedList<Integer>();

而使用LinkedList作为栈使用时，相关的API方法如下表所示：

3.代码展示

相信看到这里，解决该问题所应该具备的基础知识已经完备，接下来就可以开始进行编码了，具体的代码如下所示：

class Solution {
    public int evalRPN(String[] tokens) {
       Deque<Integer> stack=new LinkedList<Integer>();
       int length=tokens.length;
       for(int i=0;i<length;i++){
           String token=tokens[i];
           if(isNumber(token)){
               stack.push(Integer.parseInt(token));//如果是操作数，则入栈
           }else{
               int num2=stack.pop();
               int num1=stack.pop();
               switch(token){
                   case "+":
                   stack.push(num1+num2);break;
                   case "-":
                   stack.push(num1-num2);break;
                   case "*":
                   stack.push(num1*num2);break;
                   case "/":
                   stack.push(num1/num2);break;
                   default:
               }
           }
       }
       return stack.pop();
    }
    
    //判断当前字符串是否是数字
    public boolean isNumber(String number){
        return !("+".equals(number)||"-".equals(number)||"*".equals(number)||"/".equals(number));
    }
}

注意：上面的isNumber也可以使用正则表达式来进行简化，这里就不过多赘述。

该程序在LeetCode中的运行效果如下所示：