LeetCode 592 - Fraction Addition and Subtraction

作者 QIFAN 日期 2017-06-08
LeetCode 592 - Fraction Addition and Subtraction

原题链接: https://leetcode.com/problems/fraction-addition-and-subtraction/#/description


题干

给一串代表分数加减运算的字符串,以字符串形式返回结果。结果必须是最简分数形式,若结果是 2 那要返回的是 2/1

Example 1:

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

Example 2:

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

Example 3:

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

Example 4:

Input:"5/3+1/3"
Output: "2/1"

备注:

  • 输入字符串假设只有 0-9/+- 这几种字符
  • 每个分数的形式都是 ±分子/分母 ,如果结果为正, + 可以忽略
  • 输入分数的分子分母都在范围 [1,10] ,值的范围也在 [1,10]
  • 结果不会 overflow

思路

就是小学算分数的方法,分母通分,再分子相加,最后求最大公约数约分。
由于只有加法减法,可以直接从左往右运算,并且直接将运算符作为分数的符号位。

代码:

public String fractionAddition(String expression) {
int currNume = 0;
int currDeno = 1;
if (!expression.startsWith("-")) {
expression = "+" + expression;
}
int pos1 = 0;
int length = expression.length();
while (pos1 < length) {
int pos2 = pos1;
while (pos2 < length && expression.charAt(pos2) != '/') {
pos2++;
}
int nume = Integer.parseInt(expression.substring(pos1, pos2));
pos1 = ++pos2;
while (pos2 < length && expression.charAt(pos2) >= '0' && expression.charAt(pos2) <= '9') {
pos2++;
}
int deno = Integer.parseInt(expression.substring(pos1, pos2));
pos1 = pos2;
// add fractions
int combineDeno = currDeno * deno;
currNume *= deno;
nume *= currDeno;
int combineNume = currNume + nume;
int divisor = getDivisor(Math.abs(combineDeno), Math.abs(combineNume));
currNume = combineNume / divisor;
currDeno = combineDeno / divisor;
}
return currNume + "/" + currDeno;
}
private int getDivisor(int m, int n) {
int temp;
if (m < n) {
temp = m;
m = n;
n = temp;
}
if (n == 0) {
return m;
}
while (m % n != 0) {
temp = n;
n = m % n;
m = temp;
}
return n;
}