中等

问题描述

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

模拟

遍历表达式，找出所有的分数的分子分母，同时遍历过程中计算出所有分母的最小公因数，将所有分数转换成分母为它们间的最小公因数的形式计算总和，得到结果后计算出分子分母的最大公因数后进行约分操作即可。

/**
 * @param {string} expression
 * @return {string}
 */
var fractionAddition = function (expression) {
  const n = expression.length
  const numerators = []
  const denominators = []
  let i = 0
  let j = 1
  let b = 1
  const gcd = (n1, n2) => {
    return n2 > 0 ? gcd(n2, n1 % n2) : n1
  }

  const lcm = (n1, n2) => {
    return (n1 * n2) / gcd(n1, n2)
  }
  while (i < n) {
    while (j < n && expression[j] !== '+' && expression[j] !== '-') j++
    const [numerator, denominator] = expression
      .substring(i, j)
      .split('/')
      .map((i) => +i)
    numerators.push(numerator)
    denominators.push(denominator)
    b = lcm(b, denominator)
    i = j++
  }
  const a = numerators.reduce((prev, curr, idx) => prev + (b / denominators[idx]) * curr, 0)
  const g = gcd(Math.abs(a), b)
  return `${a / g}/${b / g}`
}

• 时间复杂度：$O(n + log C)$
• 空间复杂度：$O(n)$