题目描述

给定一个表示分数加减运算表达式的字符串，你需要返回一个字符串形式的计算结果。这个结果应该是不可约分的分数，即 最简分数 。如果最终结果是一个整数，例如 2，你需要将它转换成分数形式，其分母为 1。所以在上述例子中, 2 应该被转换为 2/1。

样例

输入："-1/2+1/2"
输出："0/1"

输入："-1/2+1/2+1/3"
输出："1/3"

输入："1/3-1/2"
输出："-1/6"

输入："5/3+1/3"
输出："2/1"

限制

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

算法

(模拟) $O(n)$

1. 模拟分数加减法，然后通过最大公约数约分。
2. 初始化答案为 0/1。

时间复杂度

• 遍历一次字符数，计算加减法的时间近似为常数。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Num {
public:
    int x, y;
    Num(int x_, int y_):x(x_), y(y_){}
    Num& operator += (const Num &a) {
        x = x * a.y + y * a.x;
        y = y * a.y;
        int p = __gcd(abs(x), y);
        x /= p; y /= p;
        return *this;
    }
};

class Solution {
public:
    string fractionAddition(string expression) {
        const int n = expression.size();
        Num ans(0, 1);
        int i = 0;
        while (i < n) {
            bool positive;
            if (i == 0 && isdigit(expression[i]))
                positive = true;
            else {
                positive = expression[i] == '+';
                i++;
            }
            int x = 0;
            while (i < n && isdigit(expression[i])) {
                x = x * 10 + expression[i] - '0';
                i++;
            }

            i++;

            int y = 0;
            while (i < n && isdigit(expression[i])) {
                y = y * 10 + expression[i] - '0';
                i++;
            }

            if (!positive) x = -x;
            ans += Num(x, y);
        }
        return to_string(ans.x) + "/" + to_string(ans.y);
    }
};