基本计算器II

发表于
本文字数： 3k 阅读时长 ≈ 3 分钟

LeetCode每日一题，227. Basic Calculator II

先看题目描述

6YIh11.png

大意就是给定一个字符串 s 代表一个表达式，求出表达式的值

算法和思路

栈

由于乘除运算优于加减运算，因此可以考虑先进行所有的乘除运算，并将乘除运算后的结果放回原表达式的相应位置，最后整个表达式进行加减运算，便可得到结果

基于此，我们可以用一个栈，保存这些整数值，当遇到加减号后的数字时，将其直接压入栈中；遇到乘除号后的数字时，将其与栈顶元素进行计算，并用结果替换原栈顶元素

具体到实现上，遍历字符串 s：

  • 遇到空格时，跳过
  • 遇到数字时，将数字直接压入栈中
  • 遇到加号时，将其后整数压入栈中
  • 遇到减号时，将其后整数的相反数压入栈中
  • 遇到乘号或除号时，将栈顶元素出栈，与符号后的整数进行相应运算，并将运算结果压入栈中

最后将栈中所有元素出栈，进行加法运算即可

算法源码

栈

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class Solution {
    public int calculate(String s) {
        int len = s.length();
        char[] cs = s.toCharArray();
        Deque<Integer> stack = new ArrayDeque<>();
        int index = 0;
        while (index < len) {
            char c = cs[index];
            if (c == ' ') {
                index++;
            } else if (c == '+') {
                index++;
                while (index < len && cs[index] == ' ') {
                    index++;
                }
                int num = 0;
                while (index < len && Character.isDigit(cs[index])) {
                    num = num * 10 + cs[index] - '0';
                    index++;
                }
                stack.push(num);
            } else if (c == '-') {
                index++;
                while (index < len && cs[index] == ' ') {
                    index++;
                }
                int num = 0;
                while (index < len && Character.isDigit(cs[index])) {
                    num = num * 10 + cs[index] - '0';
                    index++;
                }
                stack.push(-num);
            } else if (c == '*') {
                index++;
                while (index < len && cs[index] == ' ') {
                    index++;
                }
                int num = 0;
                while (index < len && Character.isDigit(cs[index])) {
                    num = num * 10 + cs[index] - '0';
                    index++;
                }
                stack.push(stack.pop() * num);
            } else if (c == '/') {
                index++;
                while (index < len && cs[index] == ' ') {
                    index++;
                }
                int num = 0;
                while (index < len && Character.isDigit(cs[index])) {
                    num = num * 10 + cs[index] - '0';
                    index++;
                }
                stack.push(stack.pop() / num);
            } else {
                int num = 0;
                while (index < len && Character.isDigit(cs[index])) {
                    num = num * 10 + cs[index] - '0';
                    index++;
                }
                stack.push(num);
            }
        }
        int res = 0;
        while (!stack.isEmpty()) {
            res += stack.pop();
        }
        return res;
    }
}