力扣刷题之分数加减运算（每日一题7/27）

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

来源：力扣（LeetCode） 链接

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

输入的字串是数字类型的字符，并且中间有着运算符号，并且是按照分数的形式给出。 分子与分母的范围需要注意是[1,10]。 输出要求最简，并且如果是负数的话要给出符号，反之不给。

这里面需要注意一些细节。

今天的一种解题方法，思路就是去分别计算每个分数的分子和分母。我们可以去初始化分子分母，那就是分子为0，分母为1。后面我们会获取输入的字符串的分子和分母，然后利用公式去计算。

每次获取下一个分数后，我们就想办法把其加到我们的当然分数上，一次。当然这里面还是有许多细节。我们分开层次去分析。 下面numerator 分子，denominator 分母，使我们初始化的一个分数，其实就是0,这样构造了一个初始化的值为0的分数

首先呢，我们需要对这个字符串进行遍历了。这是一个整体的for循环，之后所有的处理逻辑都在这个for循环里面进行。我们需要记录分数的符号，主要就是记录分子前面的符号，并设置一个记录符号的变量。，然后我们记录完后，往后移动。就是下面这一段。

long numerator = 0, denominator = 1;
        int length = expression.length();
        // 遍历每个字符
        for (int i = 0; i < length;) {
            // 首先记录正负符号
            int sign = expression.charAt(i) == '-' ? -1 : 1;

            // 遇到运算符指针后移
            if (expression.charAt(i) == '-' || expression.charAt(i) == '+') {
                i++;
            }

复制

下面这部分就是去计算遍历的分子和分母 顺着前面的顺序下来，分子一定是在‘/’符号前面。所以我们要这样去判断。 需要注意的是这里 num = num*10+expression.charAt(i++) - ‘0’; chartAt()函数代表取当前索引的字符，这个字符啊我们要转换为数字，所以减去了字符‘0’。但是这里为什么还会有定义的num然后乘以10呢？ 是因为如果分子是10，上面已经说了，我们的分子的范围可以取到10，那么要取到这个分子10就必须扩展位数，如果你的分子小于10的话大可不必用num处理。

假如遇到了10，我们的首先获取到的是1，然后我们转换了为数字1，假如你没有乘以10，那么现在就是1，我们后面再移动一位是0,那么你这会接收到的就是0，这样你是无法正确接收到分子的。如果乘以了10,那么一开始就是1，此时num为1然后呢，因为后面有一个0，这个循环再进行一次的时候就会1*10加上0这样可以得出正确的分子。下面的分母的原理与之相同。

   // 计算当前的分子
            long num = 0;
            while (i < length && expression.charAt(i) != '/'){
                num = num*10+expression.charAt(i++) - '0';
            }
            i++;

            // 计算当前的分母
            long den = 0;
            while (i < length && expression.charAt(i) != '+' && expression.charAt(i) != '-'){
                den = den*10+ expression.charAt(i++) - '0';
            }

            // 分母不能为0，如果出现了0，说明是整数，这里分母置为1就行
            if (den == 0) {
                den++;
            }

复制

下面就是对每一回得出的分子和分母进行一个相加。然后算出一个与下次分数相加的当前分数。

            // 计算分母的最小公倍数
          long lcm = denominator * den / gcd(denominator, den);
            // 计算新分子
            numerator = numerator * lcm / denominator + sign * num * lcm / den;
//            // 计算新分母
            denominator = lcm;

        }

复制

这里我们用到了一个计算最小公倍数，它这里调用了一个gcd（）方法，来看这个方法

     //最大公约数
    public long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }

复制

其实就是辗转相除法。 这个是一个计算最大公约数的方法，也叫作最大公因数。原理在这里。 辗转相除法。 两个分母相乘，然后除以最大公约数那么就是最小公倍数了。我们最后是要求最简的，那么我们这里这个两分母的最小公倍数自然可以作为新的分母。 新的分子的计算就是两分子分别乘以分母最小公倍数，然后再除以各自的分母所得的值相加，自己可以列个数学式子比划一下就明白了。

然后这样所得的值作为当前得分子和分母，继续遍历相加。一样的道理。 最后得到最后的值。

最后呢，我们需要进行一个最简的分数。 这次是求分母和分子的最大公约数，这里要注意分子的符号，我们这里是不要符号的，符号的最终我们用之前的符号的标记变量。

  long g = gcd(denominator, Math.abs(numerator));

复制

然后构造，并返回字符串。 求出最大公约数后就进行简化分子分母，然后转换为字符串，然后进行一个最终的拼接。

复制

完整代码

 return Long.toString(numerator / g) + "/" + Long.toString(denominator / g);

复制

完整代码

class Solution {
    public String fractionAddition(String expression) {
        // 分子与分母
        long numerator = 0, denominator = 1;
        int length = expression.length();
        // 遍历每个字符
        for (int i = 0; i < length;) {
            // 首先记录正负符号
            int sign = expression.charAt(i) == '-' ? -1 : 1;

            // 遇到运算符指针后移
            if (expression.charAt(i) == '-' || expression.charAt(i) == '+') {
                i++;
            }

            // 计算当前的分子
            long num = 0;
            while (i < length && expression.charAt(i) != '/'){
                num = 10*num + expression.charAt(i++) - '0';
            }
            i++;

            // 计算当前的分母
             long den = 0;
            while (i < length && expression.charAt(i) != '+' && expression.charAt(i) != '-'){
                den =  10*num + expression.charAt(i++) - '0';
            }

            // 分母不能为0，如果出现了0，说明是整数，这里分母置为1就行
            if (den == 0) {
                den++;
            }

            // 计算分母的最小公倍数
            long lcm = denominator * den / gcd(denominator, den);
            // 计算新分子
            numerator = numerator * lcm / denominator + sign * num * lcm / den;
            // 计算新分母
            denominator = lcm;

        }
        // 对最终结果进行化简
        long g = gcd(denominator, Math.abs(numerator));
        return Long.toString(numerator / g) + "/" + Long.toString(denominator / g);

    }

    // 最大公约数
    public long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

复制

在力扣看大佬的解题思路，总结一下，另外还有吊毛直接正则匹配的，