# Fraction Addition and Subtraction
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/fraction-addition-and-subtraction)
Canonical: https://scaleengineer.com/dsa/problems/fraction-addition-and-subtraction
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** String
**Companies:** [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Zopsmart](https://scaleengineer.com/companies/zopsmart), [IXL](https://scaleengineer.com/companies/ixl)
---
## Problem
Given a string `expression` representing an expression of fraction addition and subtraction, return the calculation result in string format.

The final result should be an [irreducible fraction](https://en.wikipedia.org/wiki/Irreducible%5Ffraction). If your final result is an integer, change it to the format of a fraction that has a denominator `1`. So in this case, `2` should be converted to `2/1`.

**Example 1:**

**Input:** expression = "-1/2+1/2"
**Output:** "0/1"

**Example 2:**

**Input:** expression = "-1/2+1/2+1/3"
**Output:** "1/3"

**Example 3:**

**Input:** expression = "1/3-1/2"
**Output:** "-1/6"

**Constraints:**

* The input string only contains `'0'` to `'9'`, `'/'`, `'+'` and `'-'`. So does the output.
* Each fraction (input and output) has the format `±numerator/denominator`. If the first input fraction or the output is positive, then `'+'` will be omitted.
* The input only contains valid **irreducible fractions**, where the **numerator** and **denominator** of each fraction will always be in the range `[1, 10]`. If the denominator is `1`, it means this fraction is actually an integer in a fraction format defined above.
* The number of given fractions will be in the range `[1, 10]`.
* The numerator and denominator of the **final result** are guaranteed to be valid and in the range of **32-bit** int.

# Approaches
## Regular Expression Based Parsing
This approach leverages regular expressions to simplify the task of parsing the input string. A regex pattern is defined to identify and extract each fraction, including its sign, numerator, and denominator. These extracted fractions are then iteratively added to a running total.
**Time:** O(L + N * log(K)), where L is the length of the expression, N is the number of fractions, and K is the magnitude of intermediate numerators/denominators. The `matcher.find()` operation scans the string, contributing O(L). The loop runs N times, with each step dominated by the GCD calculation. · **Space:** O(L), where L is the length of the expression. This space is used to store the input string and internal state for the regex matcher.
**Pros:** The parsing logic is concise and declarative, handled by the regex engine.
**Cons:** Can be less performant than a manual scan due to the overhead of regex compilation and execution.; Regex patterns can sometimes be tricky to write and debug for all edge cases.
### Explanation
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`.

```java
import java.util.regex.Matcher;
import java.util.regex.Pattern;

class Solution {
    public String fractionAddition(String expression) {
        Pattern pattern = Pattern.compile("([+-]?)(\\d+)/(\\d+)");
        Matcher matcher = pattern.matcher(expression);

        long totalNumerator = 0;
        long totalDenominator = 1;

        while (matcher.find()) {
            String signStr = matcher.group(1);
            long num = Long.parseLong(matcher.group(2));
            long den = Long.parseLong(matcher.group(3));

            if (signStr.equals("-")) {
                num = -num;
            }

            totalNumerator = totalNumerator * den + num * totalDenominator;
            totalDenominator = totalDenominator * den;

            long commonDivisor = gcd(Math.abs(totalNumerator), totalDenominator);
            totalNumerator /= commonDivisor;
            totalDenominator /= commonDivisor;
        }

        return totalNumerator + "/" + totalDenominator;
    }

    private long gcd(long a, long b) {
        while (b != 0) {
            long temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}
```
### Algorithm
*   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.

## Single-Pass Iterative Parsing
This is the most efficient approach. It involves manually scanning the input string from left to right in a single pass. By keeping track of the current position with an index, we parse each fraction's components (sign, numerator, denominator) and immediately incorporate it into a running sum. This avoids the overhead associated with regular expressions.
**Time:** O(N * log(K)), where N is the number of fractions and K is the magnitude of intermediate values. The string is traversed once, and for each fraction, a GCD calculation is performed. This is more efficient than the regex approach due to lower constant factors. · **Space:** O(1) extra space, as we only use a few variables to store the running total and the current index.
**Pros:** Highly efficient with no external library overhead for parsing.; Provides fine-grained control over the parsing logic, leading to better performance.
**Cons:** The implementation is more verbose compared to using regex.; Requires careful manual management of the string index to avoid errors.
### Explanation
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.

```java
class Solution {
    public String fractionAddition(String expression) {
        long totalNumerator = 0;
        long totalDenominator = 1;
        int i = 0;
        int n = expression.length();

        while (i < n) {
            // 1. Parse sign
            int sign = 1;
            if (expression.charAt(i) == '+' || expression.charAt(i) == '-') {
                if (expression.charAt(i) == '-') {
                    sign = -1;
                }
                i++;
            }

            // 2. Parse numerator
            long num = 0;
            while (i < n && Character.isDigit(expression.charAt(i))) {
                num = num * 10 + (expression.charAt(i) - '0');
                i++;
            }
            num *= sign;

            // Skip '/'
            i++;

            // 3. Parse denominator
            long den = 0;
            while (i < n && Character.isDigit(expression.charAt(i))) {
                den = den * 10 + (expression.charAt(i) - '0');
                i++;
            }

            // 4. Add fraction to total
            totalNumerator = totalNumerator * den + num * totalDenominator;
            totalDenominator = totalDenominator * den;

            // 5. Simplify
            long commonDivisor = gcd(Math.abs(totalNumerator), totalDenominator);
            totalNumerator /= commonDivisor;
            totalDenominator /= commonDivisor;
        }

        return totalNumerator + "/" + totalDenominator;
    }

    private long gcd(long a, long b) {
        while (b != 0) {
            long temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}
```
### Algorithm
*   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.

# Solutions
### Java

```java
class Solution {
public
  String fractionAddition(String expression) {
    int x = 0, y = 6 * 7 * 8 * 9 * 10;
    if (Character.isDigit(expression.charAt(0))) {
      expression = "+" + expression;
    }
    int i = 0, n = expression.length();
    while (i < n) {
      int sign = expression.charAt(i) == '-' ? -1 : 1;
      ++i;
      int j = i;
      while (j < n && expression.charAt(j) != '+' &&
             expression.charAt(j) != '-') {
        ++j;
      }
      String s = expression.substring(i, j);
      String[] t = s.split("/");
      int a = Integer.parseInt(t[0]), b = Integer.parseInt(t[1]);
      x += sign * a * y / b;
      i = j;
    }
    int z = gcd(Math.abs(x), y);
    x /= z;
    y /= z;
    return x + "/" + y;
  }
private
  int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
}

```

### JavaScript

```javascript
/** * @param {string} expression * @return {string} */ var fractionAddition =
  function (expression) {
    let x = 0,
      y = 1;
    if (!expression.startsWith(" - ") && !expression.startsWith(" + ")) {
      expression = " + " + expression;
    }
    let i = 0;
    const n = expression.length;
    while (i < n) {
      const sign = expression[i] === " - " ? -1 : 1;
      i++;
      let j = i;
      while (j < n && expression[j] !== " + " && expression[j] !== " - ") {
        j++;
      }
      const [a, b] = expression.slice(i, j).split(" / ").map(Number);
      x = x * b + sign * a * y;
      y *= b;
      i = j;
    }
    const gcd = (a, b) => {
      while (b !== 0) {
        [a, b] = [b, a % b];
      }
      return Math.abs(a);
    };
    const z = gcd(x, y);
    x = Math.floor(x / z);
    y = Math.floor(y / z);
    return ` ${x} / ${y} `;
  };

```

### Python

```python
class Solution:
    def fractionAddition(self, expression: str) -> str: x, y = 0, 6 * 7 * 8 * 9 * 10 if expression[0]. isdigit(): expression = '+' + expression i, n = 0, len(expression) while i < n: sign = - 1 if expression[i] == '-' else 1 i += 1 j = i while j < n and expression[j] not in '+-': j += 1 s = expression[i: j] a, b = s . split('/') x += sign * int(a) * y // int(b) i = j z = gcd(x, y) x //= z y //= z return f ' { x } / { y } '

```