力扣 150. 逆波兰表达式求值

题目说明

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

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

  • 整数除法只保留整数部分。
  • 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
  • 1 <= tokens.length <= 10^4
  • tokens[i] 要么是一个算符（"+"、"-"、"*" 或 "/"），要么是一个在范围 [-200, 200] 内的整数

示例

例1

1
2
3
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

例2

1
2
3
输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

例3

1
2
3
4
5
6
7
8
9
10
11
输入：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
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
56
import java.util.regex.*;

class Solution {
    //定义匹配规则：零或一个-号以及至少一个0-9的多个数字
    static Pattern pattern = Pattern.compile("-?[0-9]+");

    public static int evalRPN(String[] tokens) {
        int result = 0;

        Deque stack = new LinkedList<String>();

        String symbol = "";

        //字符串匹配器
        Matcher isNum;
        int num = 0;
        int temp = 0;

        //将第一个数填入栈
        stack.offer(tokens[0]);

        for (int i = 1; i < tokens.length; i++) {
            isNum = pattern.matcher(tokens[i]);
            if(isNum.matches()) {
                //当前字符串是数字，填入栈
                stack.offer(tokens[i]);
            }
            else {
                symbol = tokens[i];
                temp = Integer.parseInt((String) stack.pollLast());

                //碰掉符号就开始操作前两个数
                switch (symbol) {
                    case "+" :
                        num = Integer.parseInt((String) stack.pollLast()) + temp;
                        break;
                    case "-" :
                        num = Integer.parseInt((String) stack.pollLast()) - temp;
                        break;
                    case "*" :
                        num = Integer.parseInt((String) stack.pollLast()) * temp;
                        break;
                    case "/" :
                        num = Integer.parseInt((String) stack.pollLast()) / temp;
                        break;
                    default:
                }

                //两数运算结构填入栈
                stack.offer("" + num);
            }
        }

        return Integer.parseInt((String) stack.peek());
    }
}

咳咳，时间和空间效率都比较一般，就不贴图了；

总结

本题是今天的每日一题，难度是为中等，感兴趣的朋友都可以去尝试一下，此题还有其他更多的解法，朋友们可以自己逐一尝试。