一、题目
给定一个表示分数加减运算的字符串 expression，你需要返回一个字符串形式的计算结果。
这个结果应该是不可约分的分数，即：最简分数。 如果最终结果是一个整数，例如 2，你需要将它转换成分数形式，其分母为 1。所以在上述例子中, 2 应该被转换为 2/1。
二、示例
2.1> 示例 1：
【输入】expression = "-1/2+1/2"
【输出】"0/1"
2.2> 示例 2：
【输入】expression = "-1/2+1/2+1/3"
【输出】"1/3"
2.3> 示例 3：
【输入】expression = "1/3-1/2"
【输出】 "-1/6"
提示:
- 输入和输出字符串只包含
'0'到'9'的数字，以及'/','+'和'-'。
- 输入和输出分数格式均为
±分子/分母。如果输入的第一个分数或者输出的分数是正数，则'+'会被省略掉。
- 输入只包含合法的最简分数，每个分数的分子与分母的范围是
[1,10]。 如果分母是1，意味着这个分数实际上是一个整数。
- 输入的分数个数范围是
[1,10]。
- 最终结果的分子与分母保证是
32位整数范围内的有效整数。
三、解题思路
首先，通过题意，我们可以获得一个分数加减运算的字符串，由于计算公式中只有加法和减法，所以我们可以通过这两个符号对整个字符串进行字符串的拆分，将分数先拆分出来。如果是通过一种符号进行拆分，我们可以方便的使用split(...)方法进行字符串的拆分，但是由于本道题要根据加法或减法进行拆分，那么我们就需要采用indexOf(...)方法来确定加法或减法符号的具体位置，再根据返回值最小（即：哪一个在前面）来确定执行加法还是减法操作。在这里还有一个细节，就是如果第一个分数是负数的话，我们会将其负号判断为减号，所以，为了避免这种情况发生，我们从index=1的位置开始判断。即：调用indexOf("+", 1)和indexOf("-", 1)这两种方法。第一次符号判定的具体操作如下图所示：
由于两个分数的计算规则是：A/B + C/D = (AD + BC)/BD 或者 A/B - C/D = (AD - BC)/BD，所以无论是多少个分数相加，即：N个，我们都可以通过((N(1) * N(2)) * N(3)) * N(4)....以此类推。那么当我们查找到第一个加号/减号的时候，就可以对A和B进行赋值，那么通过while循环遍历下一个加号/减号，遍历到之后，再赋值给C和D。此时，通过(AD + BC)/BD或者(AD - BC)/BD计算出两个分数的结果后，再将结果的分子赋值给A，将分母赋值给B。然后再通过while进行下一轮的循环，获得的最新值依然赋值C和D，然后再进行两个分子的计算。以此类推。如下是第二轮符号判定的具体操作如下图所示：
那么当循环到最后一个加号、减号的时候，大家要注意，在这个符号的后面，还“残留”着最后一个分数。当所有分数计算完毕后，我们将最终结果的分子和分母作为入参，调用gcd(int A, int B)方法，该方法的目的是寻求A和B这两个数的最大公约数。因为假设我们计算出的结果是4/12，我们需要循环4和12的最大公约数——即：4，然后通过分子和分母分别除以4，来获得最终的结果，即：1/3。如下是最后一轮符号判定的具体操作如下图所示：
获得最大公约数我们可以采取辗转相除法。即：取两个数中最大的数做除数，较小的数做被除数，用最大的数除较小数，如果余数为0，则较小数为这两个数的最大公约数，如果余数不为0，用较小数除上一步计算出的余数，直到余数为0，则这两个数的最大公约数为上一步的余数。请看下面示例：
- 求100与32的最大公约数是多少？
100 ÷ 32 = 3 ... 4
32 ÷ 4 = 8 ... 0
所以：最大公约数等于4。- 求96与78的最大公约数是多少？
96 ÷ 78 = 1 ... 18
78 ÷ 18 = 4 ... 6
18 ÷ 6 = 3 ... 0
所以：最大公约数等于6。
通过上面的介绍，我们可以得出辗转相除法的模板代码，如下所示：
四、代码实现
public class Solution {
public String fractionAddition(String expression) {
int end = 0;
int minusIndex = expression.indexOf("-", 1); // 防止第一个数是负数，将其当做减号
int plusIndex = expression.indexOf("+", 1);
Integer A = null, B = null, C, D;
boolean isPlus = true; // 是否是加法运算，默认加法
while (true) {
minusIndex = minusIndex == -1 ? expression.length() : minusIndex;
plusIndex = plusIndex == -1 ? expression.length() : plusIndex;
String numStr = expression.substring(0, (end = Math.min(minusIndex, plusIndex)));
if (A == null && B == null) {
A = Integer.valueOf(numStr.split("/")[0]); // 分子
B = Integer.valueOf(numStr.split("/")[1]); // 分母
} else {
C = Integer.valueOf(numStr.split("/")[0]);
D = Integer.valueOf(numStr.split("/")[1]);
A = isPlus ? (A * D + B * C) : (A * D - B * C);
B = B * D;
}
if (expression.length() == end) {
break;
}
isPlus = plusIndex <= minusIndex;
expression = expression.substring(end + 1);
minusIndex = expression.indexOf("-");
plusIndex = expression.indexOf("+");
}
// 获得最大公约数
int gcd = gcd(A, B);
return A/gcd + "/" + B/gcd;
}
/** 获得最大公约数 */
public int gcd(int A, int B) {
int remainder = Math.abs(A) % Math.abs(B);
while (remainder != 0) {
A = B;
B = remainder;
remainder = A % B;
}
return B;
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的点赞&分享。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(o)/ ~ 「干货分享，每天更新」
题目来源：力扣（LeetCode）
