Leaky Cauldron
0%

基本计算器

Posted on Edited on

Basic Calculator 系列在 LeetCode 上有三道：

这类题目重点在于解决运算的优先级问题，需要将数字和运算符按优先级依次处理以得到正确结果。

LeetCode 224

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 1：

输入：s = “1 + 1”
输出：2

示例 2：

输入：s = “ 2-1 + 2 “
输出：3

示例 3：

输入：s = “(1+(4+5+2)-3)+(6+8)”
输出：23

题解

保存每个数字前的符号并相加。

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
class Solution {
    public int calculate(String s) {
        int n = s.length();
        int[] signs = new int[n];
        signs[0] = 1;
        int sign = 1, result = 0, sIdx = 0;

        for (int i = 0; i < n; i++) {
            char cur = s.charAt(i);

            if (cur == '+') sign = signs[sIdx];
            else if (cur == '-') sign = -signs[sIdx];
            else if (cur == '(') signs[++sIdx] = sign;
            else if (cur == ')') sIdx--;
            else if (isDigit(cur)) {
                long num = cur - '0';
                while (i + 1 < n && isDigit(s.charAt(i + 1)))
                    num = num * 10 + s.charAt(++i) - '0';
                result += sign * num;
            }
        }

        return result;
    }

    private boolean isDigit(char num) {
        return '0' <= num && num <= '9';
    }
}

LeetCode 227

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。

注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 1：

输入：s = “3+2*2”
输出：7

示例 2：

输入：s = “ 3/2 “
输出：1

示例 3：

输入：s = “ 3+5 / 2 “
输出：5

题解

先遍历计算乘除，再计算加减。

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
public class Solution {
    public int calculate(String s) {
        char sign = '+';
        int len = s.length(), idx = 0;
        int[] nums = new int[(len + 1) / 2];

        for (int i = 0; i < len; i++) {
            char cur = s.charAt(i);
            if (cur == ' ') continue;

            int num = 0;
            if (isDigit(cur)) {
                num = cur - '0';
                while (i + 1 < len && isDigit(s.charAt(i + 1)))
                    num = num * 10 - '0' + s.charAt(++i);
            }

            switch (sign) {
                case '+': nums[idx++] = num; break;
                case '-': nums[idx++] = -num; break;
                case '*': nums[idx - 1] *= num; break;
                case '/': nums[idx - 1] /= num; break;
            }

            sign = cur;
        }

        int result = 0;
        for (int i = 0; i < idx; i++) result += nums[i];

        return result;
    }

    private boolean isDigit(char ch) {
        return '0' <= ch && ch <= '9';
    }
}

LeetCode 772

实现一个基本的计算器来计算简单的表达式字符串。

表达式字符串只包含非负整数，算符 +、-、*、/ ，左括号 ( 和右括号 ) 。整数除法需要 向下截断 。

你可以假定给定的表达式总是有效的。所有的中间结果的范围为 [-231, 231 - 1] 。

示例 1：

输入：s = “1 + 1”
输出：2

示例 2：

输入：s = “6 - 4 / 2”
输出：4

示例 3：

输入：s = “2 * ( 5 + 5 * 2 ) / 3 + ( 6 / 2 + 8 )”
输出：21

示例 4：

输入：s = “( 2 + 6 * 3 + 5 - 3 * 14 / 7 + 2 ) * 5 ) + 3”
输出：-12

示例 5：

输入：s = “0”
输出：0

题解

去除括号带来的影响，相比于 227，差别仅在于将括号内的字符串递归地计算作为整体进行处理。

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
public class Solution {
    public int calculate(String s) {
        char sign = '+';
        int len = s.length(), idx = 0;
        int[] nums = new int[(len + 1) / 2];

        for (int i = 0; i < len; i++) {
            char cur = s.charAt(i);
            if (cur == ' ') continue;

            int num = 0;
            if (isDigit(cur)) {
                num = cur - '0';
                while (i + 1 < len && isDigit(s.charAt(i + 1)))
                    num = num * 10 - '0' + s.charAt(++i);
            } else if (cur == '(') {
                int j = findClosing(s.substring(i));
                num = calculate(s.substring(i + 1, i + j));
                i += j;
            }

            switch (sign) {
                case '+': nums[idx++] = num; break;
                case '-': nums[idx++] = -num; break;
                case '*': nums[idx - 1] *= num; break;
                case '/': nums[idx - 1] /= num; break;
            }

            sign = cur;
        }

        int result = 0;
        for (int i = 0; i < idx; i++) result += nums[i];

        return result;
    }

    private boolean isDigit(char ch) {
        return '0' <= ch && ch <= '9';
    }

    private int findClosing(String s) {
        int len = 0, depth = 0;

        for (char c : s.toCharArray()) {
            if (c == '(') depth++;
            else if (c == ')') {
                depth--;
                if (depth == 0) break;
            }
            len++;
        }

        return len;
    }
}