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.

思路：

单纯模拟题,Two points need to be grasped,One is the greatest common divisor,You can use tossing and dividing,但是要注意-1,比较的时候需要用abs;另一个是.First you need four numbers,upRepresents the current number numerator,downIndicates the denominator of the current number,The current number isup / down,初始化肯定是0,But avoid the denominator of 0,我们把up初始化为0,down初始化为1,不影响结果;同理使用nextup和nextdownRecord the next number,用signRecord the sign of the next number,初始化为1即可.An additional number is requiredcur,记录当前数字,因为可能是111,then each carry is required,即每次cur * 10 + 当前expression[i]的int即可.之后遍历expression,Each time a plus or minus sign is encountered, a round of calculations is performed,First if the denominator of the next number is 0,we assign1,防止分母为0.之后为nextup计算符号,Apply formula to get new oneup和down即可.Remember to reset herecur和sign,因为signis the plus or minus representing the next number,因此当前expression[i]The plus and minus signs are when the new one is calculatedup和downAssigned latersign.Finally add the last number after the traversal is complete,再得出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);
    }
};