LeetCode: 150. Evaluate Reverse Polish Notation

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

150. Evaluate Reverse Polish Notation

LeetCode - Evaluate Reverse Polish Notation

其实这只是一个栈操作。

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Note:

Division between two integers should truncate toward zero.
The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation.

Example 1:

Input: ["2", "1", "+", "3", ""]
*Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:

Input: ["4", "13", "5", "/", "+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:

Input: ["10", "6", "9", "3", "", "-11", "*", "/", "*", "17", "", "5", "+"]
Output: 22
Explanation:
  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
/**
 * Runtime: 4 ms, faster than 97.32% of Java online submissions for Evaluate Reverse Polish Notation.
 *
 * Memory Usage: 41.1 MB, less than 6.00% of Java online submissions for Evaluate Reverse Polish Notation.
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2020-01-26 16:01
 */
public int evalRPN(String[] tokens) {
    if (Objects.isNull(tokens) || tokens.length == 0) {
        return 0;
    }
    Deque<Integer> stack = new LinkedList<>();
    Set<String> operators = new HashSet<>(Arrays.asList("+", "-", "*", "/"));

    for (String token : tokens) {
        if (operators.contains(token)) {
            Integer v1 = stack.pop();
            Integer v2 = stack.pop();
            if ("+".equals(token)) {
                stack.push(v1 + v2);
                continue;
            }
            if ("-".equals(token)) {
                stack.push(v2 - v1);
                continue;
            }
            if ("*".equals(token)) {
                stack.push(v1 * v2);
                continue;
            }
            if ("/".equals(token)) {
                stack.push(v2 / v1);
                continue;
            }
        } else {
            stack.push(Integer.parseInt(token));
        }
    }

    return stack.pop();
}