0592. 分数加减运算【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 模拟
• 3. 🔗 引用

1. 📝 题目描述

• leetcode

给定一个表示分数加减运算的字符串 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 位整数范围内的有效整数。

2. 🎯 s.1 - 模拟

c

long long gcd_val(long long a, long long b) {
    while (b) { long long t = b; b = a % b; a = t; }
    return a;
}

char* fractionAddition(char* expression) {
    long long num = 0, den = 1;
    int i = 0, n = strlen(expression);
    while (i < n) {
        int sign = 1;
        if (expression[i] == '+' || expression[i] == '-') {
            if (expression[i] == '-') sign = -1;
            i++;
        }
        long long a = 0;
        while (i < n && expression[i] != '/') {
            a = a * 10 + (expression[i] - '0');
            i++;
        }
        i++;
        long long b = 0;
        while (i < n && expression[i] != '+' && expression[i] != '-') {
            b = b * 10 + (expression[i] - '0');
            i++;
        }
        a *= sign;
        num = num * b + a * den;
        den *= b;
        long long g = gcd_val(num < 0 ? -num : num, den);
        num /= g;
        den /= g;
    }
    char* res = (char*)malloc(64);
    sprintf(res, "%lld/%lld", num, den);
    return res;
}

js

/**
 * @param {string} expression
 * @return {string}
 */
var fractionAddition = function (expression) {
  let num = 0,
    den = 1
  let i = 0,
    n = expression.length
  while (i < n) {
    let sign = 1
    if (expression[i] === '+' || expression[i] === '-') {
      if (expression[i] === '-') sign = -1
      i++
    }
    let a = 0
    while (i < n && expression[i] !== '/') {
      a = a * 10 + +expression[i]
      i++
    }
    i++ // skip '/'
    let b = 0
    while (i < n && expression[i] !== '+' && expression[i] !== '-') {
      b = b * 10 + +expression[i]
      i++
    }
    a *= sign
    num = num * b + a * den
    den *= b
    const g = gcd(Math.abs(num), den)
    num /= g
    den /= g
  }
  return `${num}/${den}`
}

function gcd(a, b) {
  while (b) {
    ;[a, b] = [b, a % b]
  }
  return a
}

py

class Solution:
    def fractionAddition(self, expression: str) -> str:
        from math import gcd
        num, den = 0, 1
        i, n = 0, len(expression)
        while i < n:
            sign = 1
            if expression[i] in '+-':
                if expression[i] == '-':
                    sign = -1
                i += 1
            a = 0
            while i < n and expression[i] != '/':
                a = a * 10 + int(expression[i])
                i += 1
            i += 1
            b = 0
            while i < n and expression[i] not in '+-':
                b = b * 10 + int(expression[i])
                i += 1
            a *= sign
            num = num * b + a * den
            den *= b
            g = gcd(abs(num), den)
            num //= g
            den //= g
        return f'{num}/{den}'

• 时间复杂度：$O(n)$，其中 n 是表达式长度
• 空间复杂度：$O(1)$

算法思路：

• 逐个解析分数的分子和分母
• 每次通分后相加，再用 GCD 约分

3. 🔗 引用

• 最简分数 - 百度百科