592. Fraction Addition and Subtraction

题目：

Given a string expression representing an expression of fraction addition and subtraction, return the calculation result in string format.

The final result should be an irreducible fraction. If your final result is an integer, change it to the format of a fraction that has a denominator 1. So in this case, 2 should be converted to 2/1.

Example 1:

Input: expression = "-1/2+1/2"
Output: "0/1"

Example 2:

Input: expression = "-1/2+1/2+1/3"
Output: "1/3"

Example 3:

Input: expression = "1/3-1/2"
Output: "-1/6"

Constraints:

• The input string only contains '0' to '9', '/', '+' and '-'. So does the output.
• Each fraction (input and output) has the format ±numerator/denominator. If the first input fraction or the output is positive, then '+' will be omitted.
• The input only contains valid irreducible fractions, where the numerator and denominator of each fraction will always be in the range [1, 10]. If the denominator is 1, it means this fraction is actually an integer in a fraction format defined above.
• The number of given fractions will be in the range [1, 10].
• The numerator and denominator of the final result are guaranteed to be valid and in the range of 32-bit int.

思路：

单纯模拟题，需要掌握两点，一个是最大公约数，用辗转相除法即可，但是要注意-1，比较的时候需要用abs；另一个是。首先需要四个数，up表示当前数分子，down表示当前数分母，当前数即up / down，初始化肯定是0，但是避免分母为0，我们把up初始化为0，down初始化为1，不影响结果；同理使用nextup和nextdown记录下一个数，用sign记录下一个数的正负，初始化为1即可。另外需要一个数为cur，记录当前数字，因为可能是111，则需要每次进位，即每次cur * 10 + 当前expression[i]的int即可。之后遍历expression，每次遇到加号或者减号就进行一轮计算，首先如果下个数字的分母是0，我们赋为1，防止分母为0。之后为nextup计算符号，套用公式获得新的up和down即可。这里记得重置cur和sign，因为sign是代表下一个数字的正负，因此当前expression[i]的加减号是当计算完新的up和down以后才赋值给sign。最后在遍历完成后加上最后一个数，再得出gcd，对up和down都除以最大公约数，再转成string就是答案了。

代码：

class Solution {
public:
    string fractionAddition(string expression) {
        int up = 0, down = 1;
        int i = 0, sign = 1;
        int nextup = 0, nextdown = 1;
        int cur = 0;
        while (i < expression.size()) {
            if (expression[i] == '-') {
                nextdown = cur == 0 ? 1 : cur;
                nextup *= sign;
                up = up * nextdown + down * nextup;
                down = down * nextdown;
                sign = -1;
                cur = 0;
            } else if (expression[i] == '+') {
                nextdown = cur == 0 ? 1 : cur;
                nextup *= sign;
                up = up * nextdown + down * nextup;
                down = down * nextdown;
                sign = 1;
                cur = 0;

            } else if (expression[i] == '/') {
                nextup = cur;
                cur = 0;
            } else {
                cur = cur * 10 + (expression[i] - '0');
            }
            i++;
        }
        nextdown = cur == 0 ? 1 : cur;
        nextup *= sign;
        up = up * nextdown + down * nextup;
        down = down * nextdown;
        sign = up >= 0 ? 1 : -1;
        int g = abs(gcd(up, down));
        up /= g;
        down /= g;
        string ans = to_string(up) + '/' + to_string(down);
        return ans;
    }
private:
    int gcd(int a, int b) {
        if (abs(a) < abs(b))
            return gcd(b, a);
        if (b == 0)
            return a;
        return gcd(a % b, b);
    }
};