【字符串, 模拟】分数加减运算

题目

592. 分数加减运算

---

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

解题

方法一：字符串 模拟

思路

把整个表达式按照 '+' 或 '-' 分割为单独的分数，分割出来的分数两两累加（分出第一个分数时，累加的结果(ans)为空串，直接把该分数赋值给累加值）。

分数相加：输入的两个分数先分出4个数然后直接做分数加和（$\frac{a_1}{a_2}+\frac{b_1}{b_2}=\frac{a_1 \times b_2 + a_2 \times b_1}{a_2 \times b_2}$），分子如果为负数则把结果分数初始化为 "-" 否则为空，然后求出分子的绝对值与分母的最大公因数，分子分母同除最大公因数加入结果分数中返回。

代码

class Solution {
    public String fractionAddition(String expression) {
        int n = expression.length();
        char[] chs = expression.toCharArray();
        String ans = "", frac;
        for (int i = 0; i < n; ) {
            int j = i + 1;
            while (j < n && chs[j] != '+' && chs[j] != '-') j++;
            frac = expression.substring(i, j);
            ans = "".equals(ans) ? frac : clac(frac, ans);
            i = j;
        }
        return ans;
    }

    private String clac(String a, String b) {
        int splitA = a.indexOf('/'), splitB = b.indexOf('/');
        int a1 = Integer.parseInt(a.substring(0, splitA)), a2 = Integer.parseInt(a.substring(splitA + 1));
        int b1 = Integer.parseInt(b.substring(0, splitB)), b2 = Integer.parseInt(b.substring(splitB + 1));
        int m = a1 * b2 + a2 * b1, n = a2 * b2;
        StringBuilder res = new StringBuilder(m < 0 ? "-" : "");
        int mnGCD = gcd(m = Math.abs(m), n);
        res.append(m / mnGCD).append('/').append(n / mnGCD);
        return res.toString();
    }

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

class Solution {
public:
    string clac(const string &a, const string &b) {
        int splitA = a.find('/'), splitB = b.find('/');
        int a1 = stoi(a.substr(0, splitA)), a2 = stoi(a.substr(splitA + 1));
        int b1 = stoi(b.substr(0, splitB)), b2 = stoi(b.substr(splitB + 1));
        int m = a1 * b2 + a2 * b1, n = a2 * b2;
        string res;
        if (m < 0) {
            res += '-';
            m = -m;
        }
        int gcd = __gcd(m, n);
        res += to_string(m / gcd) + "/" + to_string(n / gcd);
        return res;
    }

    string fractionAddition(string expr) {
        int n = expr.length();
        string ans, frac;
        for (int i = 0, j = 1; i < n; i = j, j++) {
            while (j < n && expr[j] != '+' && expr[j] != '-') j++;
            frac = expr.substr(i, j - i);
            ans = ans == "" ? frac : clac(ans, frac);
        }
        return ans;
    }
};