Concise Java Solution


  • 11
    public String fractionAddition(String expression) {
        String[] fracs = expression.split("(?=[-+])"); // splits input string into individual fractions
        String res = "0/1";
        for (String frac : fracs) res = add(res, frac); // add all fractions together
        return res;
    }
    
    public String add(String frac1, String frac2) {
        int[] f1 = Stream.of(frac1.split("/")).mapToInt(Integer::parseInt).toArray(), 
              f2 = Stream.of(frac2.split("/")).mapToInt(Integer::parseInt).toArray();
        int numer = f1[0]*f2[1] + f1[1]*f2[0], denom = f1[1]*f2[1];
        String sign = "";
        if (numer < 0) {sign = "-"; numer *= -1;}
        return sign + numer/gcd(numer, denom) + "/" + denom/gcd(numer, denom); // construct reduced fraction
    }
    
    // Computes gcd using Euclidean algorithm
    public int gcd(int x, int y) { return x == 0 || y == 0 ? x + y : gcd(y, x % y); }
    

  • 0

    i think we can use the magic number "2520" instead of invoking gcd() multiple times:

    import java.util.ArrayList;
    
    public class Solution {
        public String fractionAddition(String expression) {
            if (expression.charAt(0) != '-') expression = "+" + expression;
            int positive = expression.charAt(0) == '-' ? -1 : 1, num = 0;
            ArrayList<Integer> numerators = new ArrayList<>(), denominators = new ArrayList<>();
            for (char c : expression.toCharArray()) {
                if (c == '+' || c == '-') {
                    denominators.add(num);
                    num = 0;
                    positive = c == '+' ? 1 : -1;
                } else if (c == '/') {
                    numerators.add(positive * num);
                    num = 0;
                    positive = 1;
                } else {
                    num = num * 10 + (c - 48);
                }
            }
            denominators.add(num);
    
            int sum = 0;
            for (int i = 0; i < numerators.size(); i++) {
                sum += numerators.get(i) * 2520 / denominators.get(i + 1);
            }
            int k = GCD(sum, 2520);
            return k < 0
                    ? "-" + String.valueOf(sum / k) + "/" + String.valueOf(-2520 / k)
                    : String.valueOf(sum / k) + "/" + String.valueOf(2520 / k);
        }
    
        private int GCD(int a, int b) {
            return b == 0 ? a : GCD(b, a % b);
        }
    }
    

  • 2
    B

    @compton_scatter

    Could you please explain what does ?= does in the regex?
    I can intuitively get an idea that it retains the sign also. But I would like to know the generic purpose of this syntax.

    Thanks.


  • 0

  • 1
    A

    Thanks for your nice solution. Just a small suggestion for the last part of add function. You don't need a sign and you just need to use gcd function once. Since denom is positive, the result is only decided by whether numer is positive if we use the absolute value of gcd.

    int numer = f1[0]*f2[1] + f1[1]*f2[0], denom = f1[1]*f2[1];
    int g = Math.abs(gcd(numer, denom));
    return numer / g + "/" + denom / g;

  • 3
    L

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

    Thus, expression.split("(?=[-,+])") is to split expression at the positions whose next element is either - or +. For example, when expression = "-1/2+1/2-1/3", expression.split("(?=[-,+])") generates an array of strings ["-1/2","+1/2", "-1/3"].


  • 0
    D

    Here is my similar solution

        public String fractionAddition(String expression) {
            String[] tokens = expression.split("(?=[+-])");
            int len = tokens.length;
            int[] numerators = new int[len];
            int[] denominators = new int[len];
            for (int i = 0; i < len; i++) {
                numerators[i] = Integer.parseInt(tokens[i].split("/")[0]);
                denominators[i] = Integer.parseInt(tokens[i].split("/")[1]);
            }
            long denominator = 1, numerator = 0;
            for (int i = 0; i < len; i++) {
                denominator *= denominators[i];
            }
            for (int i = 0; i < len; i++) {
                numerator += denominator * numerators[i] / denominators[i];
            }
            long A = Math.abs(gcd(denominator, numerator));
            String res = numerator / A + "/" + denominator / A;
            return res;
        }
        private long gcd (long x , long y) {
            if (y == 0) return x;
            else return gcd(y, x % y);
        }

  • 0

    @compton_scatter said in Concise Java Solution:

    (?=[-,+])

    Can you explain why you'd have comma in the regex please?


  • 0
    D

    @kekezi [ ] means that match any one in the bracket. So [+-] means it can separate a string by + or -. ?= means start from the beginning. If we do not use ?=, for example "3+2+1", the result will just be 1 (ignoring 3+2+). ( ) just means a group.


Log in to reply
 

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