# 0592. Fraction Addition and Subtraction

https://leetcode.com/problems/fraction-addition-and-subtraction

## Description

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_fraction). If your final result is an integer, say `2`, you need to 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"
```

**Example 4:**

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

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

## ac

```java
class Solution {
    public String fractionAddition(String expression) {
        List<int[]> list = extract(expression);
        int num = list.get(0)[0], den = list.get(0)[1];
        for (int i = 1; i < list.size(); i++) {
            int[] v = list.get(i);
            int d = getDeno(den, v[1]);
            num = num * (d / den) + v[0] * (d / v[1]);
            den = d;
        }

        if (num == 0) return "0/1";
        int gcd = gcd(Math.abs(num), den);
        num /= gcd; den /= gcd;

        return num + "/" + den;
    }

    public List<int[]> extract(String expression) {
        List<int[]> res = new ArrayList<>();
        String[] strings = expression.split("-");
        for (int i = 0; i < strings.length; i++) {
            if (strings[i].length() == 0) continue;
            String[] strs = strings[i].split("\\+");
            for (int j = 0; j < strs.length; j++) {
                String[] s = strs[j].split("/");
                int[] tmp = new int[2];
                tmp[0] = Integer.parseInt(s[0]);
                if (j == 0 && i != 0) tmp[0] = - tmp[0]; // first one should be negative
                tmp[1] = Integer.parseInt(s[1]);
                res.add(tmp);
            }
        }
        return res;
    }

    public int gcd(int a, int b) {
        if (a < b) return gcd(b, a);
        while (a % b != 0) {
            int tmp = a % b;
            a = b;
            b = tmp;
        }
        return b;
    }

    public int getDeno(int a, int b) {
        return (a * b) / gcd(a, b);
    }
}

/*
1) extract numbers as int[2]; 2) add up fractions in list, with helper function gdc() and getDeno(); 3) careful, when num is 0 return "0/1"
*/
```
