# Small simple C++/Java/Python

• Keep the overall result in `A / B`, read the next fraction into `a / b`. Their sum is `(Ab + aB) / Bb` (but cancel their greatest common divisor).

C++:

``````string fractionAddition(string expression) {
istringstream in(expression);
int A = 0, B = 1, a, b;
char _;
while (in >> a >> _ >> b) {
A = A * b + a * B;
B *= b;
int g = abs(__gcd(A, B));
A /= g;
B /= g;
}
}
``````

Java:

``````public String fractionAddition(String expression) {
Scanner sc = new Scanner(expression).useDelimiter("/|(?=[-+])");
int A = 0, B = 1;
while (sc.hasNext()) {
int a = sc.nextInt(), b = sc.nextInt();
A = A * b + a * B;
B *= b;
int g = gcd(A, B);
A /= g;
B /= g;
}
return A + "/" + B;
}

private int gcd(int a, int b) {
return a != 0 ? gcd(b % a, a) : Math.abs(b);
}
``````

Python 3:
Added this after @lee215 reminded me about Python 3's `math.gcd` with his solution in the comments.

``````def fractionAddition(self, expression):
ints = map(int, re.findall('[+-]?\d+', expression))
A, B = 0, 1
for a in ints:
b = next(ints)
A = A * b + a * B
B *= b
g = math.gcd(A, B)
A //= g
B //= g
return '%d/%d' % (A, B)``````

• @StefanPochmann I like the way you use `Scanner`. I spent quite a while to write my own parser during contest :(

• Perhaps we should declare the variable to long to avoid integer overflow.

• @Jim With the given limits, I'm certain that's not necessary. But I'm not sure exactly how large the numbers can get.

• Hi, Could you please elaborate/explain the Pattern: ( "/|(?=[-+])" ).
Thanks

• Super smart way to use Scanner and regex!

Since the test cases are small, I used long to avoid overflow and calculating GCD every iteration. This is my code after stealing your idea of using Scanner:

``````public String fractionAddition1(String expression) {
Scanner s = new Scanner(expression).useDelimiter("/|(?=[-+])");
long num = 0, den = 1;
while (s.hasNext()) {
long a = s.nextLong(), b = s.nextLong();
num = num * b + a * den;
den *= b;
}
long gcd = gcd(num, den);
return (num / gcd) + "/" + (den / gcd);
}

private long gcd(long a, long b) {
if (b == 0)
return a < 0 ? -a : a;    // always return positive gcd
return gcd(b, a % b);
}``````

• Hello，I wonder what happened when `a<0` in `gcd` function in Java? Will it causes more calculation?

• Python3 version:

``````def fractionAddition(self, exp):
i, j, a, b, n = 0, 0, 0, 1, len(exp)
while j < len(exp):
i,j = j,exp.find('/', j)
a2 = int(exp[i:j])
i, j = j + 1, min(exp.find('+', j) % (n + 1), exp.find('-', j) % (n + 1))
b2 = int(exp[i:j])
a, b = a * b2 + b * a2, b * b2
a, b = a // math.gcd(a, b), b // math.gcd(a, b)
return str(a) + '/' + str(b)``````

• @lee215 Nice, I forgot they added `math.gcd`. Another Python one, I prefer the parsing to be cleanly separated:

``````def fractionAddition(self, expression):
ints = map(int, re.findall('[+-]?\d+', expression))
A, B = 0, 1
for a in ints:
b = next(ints)
A = A * b + a * B
B *= b
g = math.gcd(A, B)
A //= g
B //= g
return '%d/%d' % (A, B)
``````

Though really my first Python solution (actually my first solution overall) was this:

``````import fractions

class Solution(object):
x = eval(re.sub('(\d+)', r'fractions.Fraction(\1)', expression))
return '%d/%d' % (x.numerator, x.denominator)
``````

• @StefanPochmann
I did the same here using fractions:

``````from fractions import Fraction
class Solution(object):
res = sum(map(Fraction, exp.replace('+', ' +').replace('-', ' -').split()))
return str(res.numerator) + '/' + str(res.denominator)``````

• Could anybody please put in words on how the regex: ( "/|(?=[-+])" ) , works in this scenario.
Thanks

• _gcd

how can you use the __gcd function in C++ example.
It doesn't work in my computer.

• @guettawah Use a compiler that has it :-P (The compiler used by LeetCode does have it). Or with C++17, try this: http://en.cppreference.com/w/cpp/numeric/gcd

• @aayushgarg The (?=) part is a zero-width positive lookahead. Since [-,+] means - or +, the regex (?=[-,+]) means the next element is either - or +.

Since | is logical or operator, "/|(?=[-+])" means the element is "/", or the next element is either - or +. For example, when expression = "-1/2+1/2-1/3",

``````Scanner sc = new Scanner(expression).useDelimiter("/|(?=[-+])")
``````

generates [-1, 2, +1, 2, -1, 3 ]. Note that the signs - and + are preserved.

• This post is deleted!

• @StefanPochmann Can you please explain why we need to cancel the gcd ?

• @gshirish Because we have read the problem description. (Really I don't know what else to say)

• @StefanPochmann I got it, I didn't read the irreducible fraction. Thanks

• java code not robust:
test this one: "-1/2-1/2+---+1/3".
the above test case would throw an exception, which should work, even if it is not included in the test cases. But the judge would give a correct answer to this test case