Question

592. 分数加减运算

English Version

题目描述

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

解法

方法一：数学

class Solution:
  def fractionAddition(self, expression: str) -> str:
    x, y = 0, 6 * 7 * 8 * 9 * 10
    if expression[0].isdigit():
      expression = '+' + expression
    i, n = 0, len(expression)
    while i < n:
      sign = -1 if expression[i] == '-' else 1
      i += 1
      j = i
      while j < n and expression[j] not in '+-':
        j += 1
      s = expression[i:j]
      a, b = s.split('/')
      x += sign * int(a) * y // int(b)
      i = j
    z = gcd(x, y)
    x //= z
    y //= z
    return f'{x}/{y}'

class Solution {
  public String fractionAddition(String expression) {
    int x = 0, y = 6 * 7 * 8 * 9 * 10;
    if (Character.isDigit(expression.charAt(0))) {
      expression = "+" + expression;
    }
    int i = 0, n = expression.length();
    while (i < n) {
      int sign = expression.charAt(i) == '-' ? -1 : 1;
      ++i;
      int j = i;
      while (j < n && expression.charAt(j) != '+' && expression.charAt(j) != '-') {
        ++j;
      }
      String s = expression.substring(i, j);
      String[] t = s.split("/");
      int a = Integer.parseInt(t[0]), b = Integer.parseInt(t[1]);
      x += sign * a * y / b;
      i = j;
    }
    int z = gcd(Math.abs(x), y);
    x /= z;
    y /= z;
    return x + "/" + y;
  }

  private int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
  }
}

func fractionAddition(expression string) string {
  x, y := 0, 6*7*8*9*10
  if unicode.IsDigit(rune(expression[0])) {
    expression = "+" + expression
  }
  i, n := 0, len(expression)
  for i < n {
    sign := 1
    if expression[i] == '-' {
      sign = -1
    }
    i++
    j := i
    for j < n && expression[j] != '+' && expression[j] != '-' {
      j++
    }
    s := expression[i:j]
    t := strings.Split(s, "/")
    a, _ := strconv.Atoi(t[0])
    b, _ := strconv.Atoi(t[1])
    x += sign * a * y / b
    i = j
  }
  z := gcd(abs(x), y)
  x /= z
  y /= z
  return fmt.Sprintf("%d/%d", x, y)
}

func abs(x int) int {
  if x < 0 {
    return -x
  }
  return x
}

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