题目

题目地址：https://leetcode-cn.com/problems/evaluate-reverse-polish-notation

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

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

说明：

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

示例：

1
2
3
4
5
6
7
8
9
10
输入: ["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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
package com.jarome.leetcode;

import java.util.Stack;

public class SolutionEvalRPN {

    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            // 根据题目，tokens里只能是整数或者运算符
            String token = tokens[i];
            if (isOperator(token)) {
                // 做一个容错判断
                if (stack.size() >= 2) {
                    // 第一次出栈获取的是第二个数
                    Integer num2 = stack.pop();
                    Integer 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;
                    }
                }
            } else {
                stack.push(Integer.valueOf(token));
            }
        }
        int res = 0;
        if (!stack.isEmpty()) {
            res = stack.pop();
        }
        return res;
    }

    private boolean isOperator(String str) {
        return "+".equals(str) || "-".equals(str) || "*".equals(str) || "/".equals(str);
    }

    public static void main(String[] args) {
        String[] tokens = {"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"};
        SolutionEvalRPN sr = new SolutionEvalRPN();
        int i = sr.evalRPN(tokens);
        System.out.println(i);
    }
}