leetcode 150.逆波兰表达式求值

题目

思路

逆波兰表达式也是经典的栈的应用问题。

先说什么是逆波兰表达式（也叫后缀表达式）

我们习惯的是这样的表达式：1 + 2 / 3 ,这也叫中缀表达式。

但是对于计算机来说不好理解，当从左扫描到 2 的时候还需要再判断2后面是什么运算符，再比较一下 + 和 / 的运算符的优先级才能计算。

而逆波兰表达式是这样的： 1 2 3 / + 它没有括号，利用栈就可以顺序处理了。

我们把数字放入栈里，遇到+ - * / 的时候，将栈顶的两个元素弹出进行计算，把结果放回栈中，然后继续扫描。

基础知识

string类内部自己已经重写了equals方法，所以它比较的是字符值（equals与==的区别，面试八股）

将字符串转换成int 使用Integer.parseInt()方法

代码

import java.util.Deque;
import java.util.LinkedList;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> deque = new LinkedList<>();
        for (String s : tokens) {
            if ("+".equals(s))
                deque.push(deque.pop() + deque.pop());
            else if ("-".equals(s))
                deque.push(-deque.pop() + deque.pop());
            else if ("*".equals(s))
                deque.push(deque.pop() * deque.pop());
            else if ("/".equals(s)) {
                int b = deque.pop();
                int a = deque.pop();
                deque.push(a / b); // deque.push(1 / deque.pop() * deque.pop()) 不能写成这个，因为int类型会向下取整，如 1/5*6=0
            } else
                deque.push(Integer.parseInt(s));
        }
        int res = deque.pop();
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)