【LeetCode】150.逆波兰表达式求值

一、题目描述：根据逆波兰表示法，求表达式的值。有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

• 整数除法只保留整数部分。

• 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

二、解题思路：逆波兰表达式实际为后缀表达式，是每一运算符都置于其运算对象之后，它的优势在于只用两种简单操作，入栈和出栈就可以搞定任何普通表达式的运算。其运算方式如下：如果当前字符为变量或者为数字，则压栈，如果是运算符，则将栈顶两个元素弹出作相应运算，结果再入栈，最后当表达式扫描完后，栈里的就是结果。其中需要注意的是除法操作，需要关注数字的先后顺序，最先出栈的是除数，而后面出栈的是被除数。

三、具体实现：

class Solution {
    public int evalRPN(String[] tokens) {

        Stack<Integer> stack = new Stack<>();
        
        for(String s:tokens){
            switch(s){
                case "+":
                    stack.push(stack.pop()+stack.pop());
                    break;
                case "-":
                    stack.push(-stack.pop()+stack.pop());
                    break;
                case "*":  
                    stack.push(stack.pop() * stack.pop());
                    break;
                case "/": 
                    int num = stack.pop();                
                    stack.push(stack.pop() / num);
                    break;
                default:     
                    stack.push(Integer.valueOf(s));     
                    break;
            }
        }
        return stack.pop();
    }
}