Day 10

150. 逆波兰表达式求值

本题不难，但第一次做的话，会很难想到，所以先看视频，了解思路再去做题

题目链接：https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/

文章讲解：https://programmercarl.com/0150.逆波兰表达式求值.html

视频讲解：https://www.bilibili.com/video/BV1kd4y1o7on

（1）思路分析

内容补充：波兰表达式介绍
波兰表达式（前缀表达式）：二叉树的先序遍历
逆波兰表达式（后缀表达式）：二叉树的后序遍历

波兰表达式的优点
去掉括号后表达式无歧义，平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) ，即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

波兰表达式和栈的结合运用

遍历波兰表达式，遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

⚠️ 计算注意点

加法、乘法：满足交换律，不关心顺序，顺序不会影响表达式的结果
减法、除法：不满足交换律，关心顺序，然而元素在栈中的顺序是和表达式相反的，这里需要做处理

1. 减法：例如计算 a - b，但实际上在栈中出栈顺序应该是 b、a，为了实现 a - b，需要对第一个出栈元素做取反处理，即有如下代码

java

stack.push(-stack.pop() + stack.pop());

2. 除法：还是顺序问题，栈中的顺序和表达式顺序是相反的，也要做相应的处理，即有如下代码

java

int temp1 = stack.pop();
int temp2 = stack.pop();
stack.push(temp2 / temp1);

（2）题解

java

class Solution {
    public int evalRPN(String[] tokens) {
        // 模拟栈结构
        Deque<Integer> stack = new LinkedList();
        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)) {
                int temp1 = stack.pop();
                int temp2 = stack.pop();
                stack.push(temp2 / temp1);
            } else {
                stack.push(Integer.valueOf(s)); // 字符串转 Integer
            }
        }
        return stack.pop();
    }
}