Fraction Addition and Subtraction

• Initialize a running total fraction, totalNumerator = 0 and totalDenominator = 1.
• Define a regular expression pattern, such as ([+-]?)(\d+)/(\d+), to identify and capture the sign (optional), numerator, and denominator of each fraction.
• Use java.util.regex.Matcher to find all occurrences of this pattern in the input expression.
• Iterate through each match found by the matcher:
  • Extract the sign, numerator num, and denominator den from the matched groups.
  • Apply the sign to the numerator.
  • Add the parsed fraction num/den to the running total totalNumerator/totalDenominator. The new total is calculated as:
    • newNumerator = totalNumerator * den + num * totalDenominator
    • newDenominator = totalDenominator * den
  • To keep the numbers from growing too large, immediately simplify the new total by dividing both newNumerator and newDenominator by their Greatest Common Divisor (GCD).
• After iterating through all the fractions, format the final totalNumerator and totalDenominator into the string "<numerator>/<denominator>" and return it.

The algorithm starts by initializing a result fraction, representing the cumulative sum, to 0/1. A regular expression, such as ([+-]?)(\d+)/(\d+), is used to find all fraction components in the input string. The java.util.regex.Matcher class is employed to iterate through all matches. For each fraction c/d found, the sign, numerator c, and denominator d are parsed from the matched groups. This fraction is then added to the current total A/B using the formula A/B + c/d = (A*d + B*c) / (B*d). To prevent the intermediate numerator and denominator from becoming excessively large and to simplify the final result, we simplify the running total after each addition by dividing both the numerator and denominator by their Greatest Common Divisor (GCD). The GCD is calculated using the Euclidean algorithm. It's important to use long data types for the numerator and denominator to avoid potential integer overflow during intermediate calculations. After processing all fractions, the final result A/B is formatted into the required string A + "/" + B.

1import java.util.regex.Matcher;2import java.util.regex.Pattern;3 4class Solution {5    public String fractionAddition(String expression) {6        Pattern pattern = Pattern.compile("([+-]?)(\\d+)/(\\d+)");7        Matcher matcher = pattern.matcher(expression);8 9        long totalNumerator = 0;10        long totalDenominator = 1;11 12        while (matcher.find()) {13            String signStr = matcher.group(1);14            long num = Long.parseLong(matcher.group(2));15            long den = Long.parseLong(matcher.group(3));16 17            if (signStr.equals("-")) {18                num = -num;19            }20 21            totalNumerator = totalNumerator * den + num * totalDenominator;22            totalDenominator = totalDenominator * den;23 24            long commonDivisor = gcd(Math.abs(totalNumerator), totalDenominator);25            totalNumerator /= commonDivisor;26            totalDenominator /= commonDivisor;27        }28 29        return totalNumerator + "/" + totalDenominator;30    }31 32    private long gcd(long a, long b) {33        while (b != 0) {34            long temp = b;35            b = a % b;36            a = temp;37        }38        return a;39    }40}

• Initialize a running total fraction: totalNumerator = 0, totalDenominator = 1.
• Initialize a pointer for the string: index = 0.
• Loop while index is less than the string length:
  • Parse Sign: Check the character at index. If it's '-', the sign is -1; otherwise, it's +1. Advance index if a sign character ('+' or '-') is present.
  • Parse Numerator: Read consecutive digits starting from index to build the numerator value. Advance index past these digits.
  • Parse Denominator: Skip the '/' character. Then, read the consecutive digits that follow to build the denominator value. Advance index past these digits.
  • Add to Total: Combine the parsed fraction num/den with the running total totalNumerator/totalDenominator.
  • Simplify: Calculate the GCD of the new total's numerator and denominator and divide both by it to keep the fraction simplified.
• After the loop, format the final totalNumerator/totalDenominator into a string and return.

The core idea is to maintain a running total, initialized as the fraction 0/1. We then iterate through the expression string, parsing one fraction at a time and adding it to this total. The algorithm proceeds as follows:

1. Initialize totalNumerator = 0L, totalDenominator = 1L, and a string index i = 0.
2. Loop while i is less than the length of the expression.
3. Inside the loop, parse the next full fraction:
   • Sign: Check the character at index i. If it's '-', the sign is negative; otherwise, it's positive. Advance i if a sign character is found.
   • Numerator: Read the sequence of digits that follows to form the numerator. Advance i past these digits.
   • Denominator: Skip the '/' character. Read the next sequence of digits to form the denominator. Advance i past these digits.
4. Once a fraction num/den is parsed, add it to the running total totalNumerator/totalDenominator:
   • new_num = totalNumerator * den + num * totalDenominator
   • new_den = totalDenominator * den
5. To keep the numbers manageable and ensure the final result is simplified, immediately reduce the new total fraction by finding the Greatest Common Divisor (GCD) of the absolute value of the new numerator and the new denominator.
6. Update totalNumerator and totalDenominator by dividing them by the GCD. After the loop completes, totalNumerator/totalDenominator will hold the final, simplified answer. This is then converted to the required string format.

1class Solution {2    public String fractionAddition(String expression) {3        long totalNumerator = 0;4        long totalDenominator = 1;5        int i = 0;6        int n = expression.length();7 8        while (i < n) {9            // 1. Parse sign10            int sign = 1;11            if (expression.charAt(i) == '+' || expression.charAt(i) == '-') {12                if (expression.charAt(i) == '-') {13                    sign = -1;14                }15                i++;16            }17 18            // 2. Parse numerator19            long num = 0;20            while (i < n && Character.isDigit(expression.charAt(i))) {21                num = num * 10 + (expression.charAt(i) - '0');22                i++;23            }24            num *= sign;25 26            // Skip '/'27            i++;28 29            // 3. Parse denominator30            long den = 0;31            while (i < n && Character.isDigit(expression.charAt(i))) {32                den = den * 10 + (expression.charAt(i) - '0');33                i++;34            }35 36            // 4. Add fraction to total37            totalNumerator = totalNumerator * den + num * totalDenominator;38            totalDenominator = totalDenominator * den;39 40            // 5. Simplify41            long commonDivisor = gcd(Math.abs(totalNumerator), totalDenominator);42            totalNumerator /= commonDivisor;43            totalDenominator /= commonDivisor;44        }45 46        return totalNumerator + "/" + totalDenominator;47    }48 49    private long gcd(long a, long b) {50        while (b != 0) {51            long temp = b;52            b = a % b;53            a = temp;54        }55        return a;56    }57}