Small simple C++/Java/Python


  • 25

    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;
        }
        return to_string(A) + '/' + to_string(B);
    }
    

    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)

  • 0

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


  • 0
    J

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


  • 0

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


  • 1
    A

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


  • 1
    T

    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);
    }

  • 0
    F

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


  • 1

    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)

  • 0

    @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):
        def fractionAddition(self, expression):
            x = eval(re.sub('(\d+)', r'fractions.Fraction(\1)', expression))
            return '%d/%d' % (x.numerator, x.denominator)
    

  • 1

    @StefanPochmann
    I did the same here using fractions:

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

  • 0
    A

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


  • 0
    G

    @StefanPochmann said in Small simple C++/Java/Python:

    _gcd

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


  • 0

    @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


  • 6
    L

    @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.


  • -1
    S
    This post is deleted!

  • 0
    G

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


  • 0

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


  • 0
    G

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


  • 0
    F

    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


  • 0

    @facss That's invalid input. Please read the problem's notes.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.