Day75 逆波兰表达式求值

根据 逆波兰表示法，求表达式的值。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/

示例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 <= tokens.length <= 104
tokens[i] 要么是一个算符（"+"、"-"、"*" 或 "/"），要么是一个在范围 [-200, 200] 内的整数

Java解法

思路：

• 逆波兰表示法就是为了让计算机方便计算使用的，本身就是通过用栈来存储操作数，遇到运算符进行弹出操作数运算再入栈，直到结束
• 注意踩坑，出栈时的操作数，先出的是被操作的，注意位置顺序

package sj.shimmer.algorithm.m4_2021;

import java.util.Stack;

/**
 * Created by SJ on 2021/4/12.
 */

class D75 {
    public static void main(String[] args) {
//        System.out.println(evalRPN(new String[]{"2","1","+","3","*"}));
        System.out.println(evalRPN(new String[]{"4","13","5","/","+"}));
    }
    public static int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();

        for (String token : tokens) {
            Integer a = 0;
            Integer b = 0;
            switch (token) {
                case "+":
                    b = stack.pop();
                    a = stack.pop();
                    stack.add(a + b);
                    break;
                case "-":
                    b = stack.pop();
                    a = stack.pop();
                    stack.add(a - b);
                    break;
                case "*":
                    b = stack.pop();
                    a = stack.pop();
                    stack.add(a * b);
                    break;
                case "/":
                    b = stack.pop();
                    a = stack.pop();
                    stack.add(a / b);
                    break;
                default:
                    stack.add(Integer.parseInt(token));
                    break;
            }
        }
        return stack.pop();
    }
}

官方解

https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/solution/ni-bo-lan-biao-da-shi-qiu-zhi-by-leetcod-wue9/

1. 栈

   即我的解法

   • 时间复杂度：O(n)
   • 空间复杂度：O(n)

2. 数组模拟栈