0592-分数加减运算

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:24 2023-09-13 16:06:24 Updated    

给定一个表示分数加减运算的字符串 expression ，你需要返回一个字符串形式的计算结果。

这个结果应该是不可约分的分数，即最简分数 。
如果最终结果是一个整数，例如 2，你需要将它转换成分数形式，其分母为 1。所以在上述例子中, 2 应该被转换为 2/1。

示例 1:

**输入:**  expression = "-1/2+1/2"
**输出:** "0/1"

** 示例 2:**

**输入:**  expression = "-1/2+1/2+1/3"
**输出:** "1/3"

示例 3:

**输入:**  expression = "1/3-1/2"
**输出:** "-1/6"

提示:

  • 输入和输出字符串只包含 '0' 到 '9' 的数字，以及 '/', '+' 和 '-'。
  • 输入和输出分数格式均为 ±分子/分母。如果输入的第一个分数或者输出的分数是正数，则 '+' 会被省略掉。
  • 输入只包含合法的 最简分数 ，每个分数的 分子 与 分母 的范围是 [1,10]。 如果分母是1，意味着这个分数实际上是一个整数。
  • 输入的分数个数范围是 [1,10]。
  • 最终结果 的分子与分母保证是 32 位整数范围内的有效整数。

方法一：模拟

对于两个分数 \dfrac{x_1}{y_1} 和 \dfrac{x_2}{y_2，它们相加的结果为：

\dfrac{x_1 \times y_2 + x_2 \times y_1}{y_1 \times y_2

初始分数的分子为 x} = 0，分母为 y} = 1。我们不断从字符串中获取下一个分数，它的分子为 x}_1，分母为 y}_1，将它加到初始分数上，有：

\begin{cases}
\textit{x} = \textit{x} \times \textit{y}_1 + \textit{x}_1 \times \textit{y} \
\textit{y} = \textit{y} \times \textit{y}_1
\end{cases}

最后如果 x} = 0，说明结果为零，直接返回 “0/1”；否则计算分子分母的最大公约数，返回约简后分数的字符串表示。

[sol1-Python3]
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:
    def fractionAddition(self, expression: str) -> str:
        x, y = 0, 1  # 分子，分母
        i, n = 0, len(expression)
        while i < n:
            # 读取分子
            x1, sign = 0, 1
            if expression[i] == '-' or expression[i] == '+':
                if expression[i] == '-':
                    sign = -1
                i += 1
            while i < n and expression[i].isdigit():
                x1 = x1 * 10 + int(expression[i])
                i += 1
            x1 = sign * x1
            i += 1

            # 读取分母
            y1 = 0
            while i < n and expression[i].isdigit():
                y1 = y1 * 10 + int(expression[i])
                i += 1

            x = x * y1 + x1 * y
            y *= y1
        if x == 0:
            return "0/1"
        g = gcd(abs(x), y)
        return f"{x // g}/{y // g}"
[sol1-C++]
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
class Solution {
public:
    string fractionAddition(string expression) {
        long long x = 0, y = 1; // 分子，分母
        int index = 0, n = expression.size();
        while (index < n) {
            // 读取分子
            long long x1 = 0, sign = 1;
            if (expression[index] == '-' || expression[index] == '+') {
                sign = expression[index] == '-' ? -1 : 1;
                index++;
            }
            while (index < n && isdigit(expression[index])) {
                x1 = x1 * 10 + expression[index] - '0';
                index++;
            }
            x1 = sign * x1;
            index++;

            // 读取分母
            long long y1 = 0;
            while (index < n && isdigit(expression[index])) {
                y1 = y1 * 10 + expression[index] - '0';
                index++;
            }

            x = x * y1 + x1 * y;
            y *= y1;
        }
        if (x == 0) {
            return "0/1";
        }
        long long g = gcd(abs(x), y); // 获取最大公约数
        return to_string(x / g) + "/" + to_string(y / g);
    }
};
[sol1-Java]
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
class Solution {
    public String fractionAddition(String expression) {
        long x = 0, y = 1; // 分子，分母
        int index = 0, n = expression.length();
        while (index < n) {
            // 读取分子
            long x1 = 0, sign = 1;
            if (expression.charAt(index) == '-' || expression.charAt(index) == '+') {
                sign = expression.charAt(index) == '-' ? -1 : 1;
                index++;
            }
            while (index < n && Character.isDigit(expression.charAt(index))) {
                x1 = x1 * 10 + expression.charAt(index) - '0';
                index++;
            }
            x1 = sign * x1;
            index++;

            // 读取分母
            long y1 = 0;
            while (index < n && Character.isDigit(expression.charAt(index))) {
                y1 = y1 * 10 + expression.charAt(index) - '0';
                index++;
            }

            x = x * y1 + x1 * y;
            y *= y1;
        }
        if (x == 0) {
            return "0/1";
        }
        long g = gcd(Math.abs(x), y); // 获取最大公约数
        return Long.toString(x / g) + "/" + Long.toString(y / g);
    }

    public long gcd(long a, long b) {
        long remainder = a % b;
        while (remainder != 0) {
            a = b;
            b = remainder;
            remainder = a % b;
        }
        return b;
    }
}
[sol1-C#]
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
public class Solution {
    public string FractionAddition(string expression) {
        long x = 0, y = 1; // 分子，分母
        int index = 0, n = expression.Length;
        while (index < n) {
            // 读取分子
            long x1 = 0, sign = 1;
            if (expression[index] == '-' || expression[index] == '+') {
                sign = expression[index] == '-' ? -1 : 1;
                index++;
            }
            while (index < n && char.IsDigit(expression[index])) {
                x1 = x1 * 10 + expression[index] - '0';
                index++;
            }
            x1 = sign * x1;
            index++;

            // 读取分母
            long y1 = 0;
            while (index < n && char.IsDigit(expression[index])) {
                y1 = y1 * 10 + expression[index] - '0';
                index++;
            }

            x = x * y1 + x1 * y;
            y *= y1;
        }
        if (x == 0) {
            return "0/1";
        }
        long g = GCD(Math.Abs(x), y); // 获取最大公约数
        return (x / g).ToString() + "/" + (y / g).ToString();
    }

    public long GCD(long a, long b) {
        long remainder = a % b;
        while (remainder != 0) {
            a = b;
            b = remainder;
            remainder = a % b;
        }
        return b;
    }
}
[sol1-C]
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
#define MAX_STR_LEN 80

long long gcd(long long a, long long b) {
    long remainder = a % b;
    while (remainder != 0) {
        a = b;
        b = remainder;
        remainder = a % b;
    }
    return b;
}

char * fractionAddition(char * expression) {
    long long x = 0, y = 1; // 分子，分母
    int index = 0, n = strlen(expression);
    while (index < n) {
        // 读取分子
        long long x1 = 0, sign = 1;
        if (expression[index] == '-' || expression[index] == '+') {
            sign = expression[index] == '-' ? -1 : 1;
            index++;
        }
        while (index < n && isdigit(expression[index])) {
            x1 = x1 * 10 + expression[index] - '0';
            index++;
        }
        x1 = sign * x1;
        index++;

        // 读取分母
        long long y1 = 0;
        while (index < n && isdigit(expression[index])) {
            y1 = y1 * 10 + expression[index] - '0';
            index++;
        }

        x = x * y1 + x1 * y;
        y *= y1;
    }
    if (x == 0) {
        return "0/1";
    }
    long long g = gcd(abs(x), y); // 获取最大公约数
    char *ans = (char *)malloc(sizeof(char) * MAX_STR_LEN);
    sprintf(ans, "%d/%d", x / g, y / g);
    return ans;
}
[sol1-Golang]
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
func fractionAddition(expression string) string {
    x, y := 0, 1 // 分子，分母
    for i, n := 0, len(expression); i < n; {
        // 读取分子
        x1, sign := 0, 1
        if expression[i] == '-' || expression[i] == '+' {
            if expression[i] == '-' {
                sign = -1
            }
            i++
        }
        for i < n && unicode.IsDigit(rune(expression[i])) {
            x1 = x1*10 + int(expression[i]-'0')
            i++
        }
        x1 = sign * x1
        i++

        // 读取分母
        y1 := 0
        for i < n && unicode.IsDigit(rune(expression[i])) {
            y1 = y1*10 + int(expression[i]-'0')
            i++
        }

        x = x*y1 + x1*y
        y *= y1
    }
    if x == 0 {
        return "0/1"
    }
    g := gcd(abs(x), y)
    return fmt.Sprintf("%d/%d", x/g, y/g)
}

func gcd(a, b int) int {
    for a != 0 {
        a, b = b%a, a
    }
    return b
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}
[sol1-JavaScript]
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
var fractionAddition = function(expression) {
    let x = 0, y = 1; // 分子，分母
    let index = 0, n = expression.length;
    while (index < n) {
        // 读取分子
        let x1 = 0, sign = 1;
        if (expression[index] === '-' || expression[index] === '+') {
            sign = expression[index] === '-' ? -1 : 1;
            index++;
        }
        while (index < n && isDigit(expression[index])) {
            x1 = x1 * 10 + expression[index].charCodeAt() - '0'.charCodeAt();
            index++;
        }
        x1 = sign * x1;
        index++;

        // 读取分母
        let y1 = 0;
        while (index < n && isDigit(expression[index])) {
            y1 = y1 * 10 + expression[index].charCodeAt() - '0'.charCodeAt();
            index++;
        }

        x = x * y1 + x1 * y;
        y *= y1;
    }
    if (x === 0) {
        return "0/1";
    }
    const g = gcd(Math.abs(x), y); // 获取最大公约数
    return Math.floor(x / g) + "/" + Math.floor(y / g);
}

const gcd = (a, b) => {
    let remainder = a % b;
    while (remainder !== 0) {
        a = b;
        b = remainder;
        remainder = a % b;
    }
    return b;
};

const isDigit = (ch) => {
    return parseFloat(ch).toString() === "NaN" ? false : true;
}

复杂度分析

  • 时间复杂度：O(n + \log C)，其中 n 是字符串 expression 的长度，C 为化简前结果分子分母的最大值。求最大公约数需要 O(\log C)。

  • 空间复杂度：O(1)。

 Comments
On this page
0592-分数加减运算