Java Solution with Inline Comments


  • 0
    Z
    public class Solution {
        public String fractionAddition(String expression) {
            if (expression.isEmpty()) return "";
            // append "0/1" infront of first negative sign to make it consistent
            if (expression.charAt(0) == '-') {
                expression = "0/1" + expression;
            }
            List<Integer> numerators = new ArrayList<>();
            List<Integer> denominators = new ArrayList<>();
            List<Character> ops = new ArrayList<>();
            String[] fractions = expression.split("-|\\+");
            for (int i = 0; i < expression.length(); i++) {
                char c = expression.charAt(i);
                if (c == '-' || c == '+') ops.add(c);
            }
            for (int i = 0; i < fractions.length; i++) {
                String frac = fractions[i];  
                String[] fracTwoParts = frac.split("/");
                // always keep denominators positive
                denominators.add(Integer.parseInt(fracTwoParts[1]));
                // make sure all numerators have correct values
                if (i == 0) numerators.add(Integer.parseInt(fracTwoParts[0]));
                else numerators.add(Integer.parseInt(ops.get(i - 1) + fracTwoParts[0])); // add sign
                
            }
            return computeReduction(numerators, denominators);
        }
        
        // perform reduction
        private String computeReduction(List<Integer> numerators, List<Integer> denominators) {    
            int len = numerators.size();
            long factor = 1;
            for (int i = 0; i < len; i++) {
                factor *= denominators.get(i);
            }
            long normalizedNumerator = 0;
            for (int i = 0; i < len; i++) {
                normalizedNumerator += numerators.get(i) * factor / denominators.get(i);
            } 
            long gcd = getGCD(normalizedNumerator, factor);
            // divide them with greatest common divisor
            // correct the order so it should be "-1/6" instead of "1/-6"
            if (gcd > 0) return (normalizedNumerator / gcd) + "/" + (factor / gcd);
            else return (-normalizedNumerator / gcd) + "/" + (-factor / gcd);
                  
            
        }
        
        private long getGCD(long a, long b) {
           if (b == 0) return a;
           return getGCD(b, a % b);
        }    
    }
    

Log in to reply
 

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