# LeetCode 592: Fraction Addition and Subtraction

## Problem Restatement

We are given a string `expression` representing additions and subtractions of fractions.

Each fraction has the form:

```text
numerator/denominator
```

A fraction may have a leading `+` or `-`.

We need to evaluate the whole expression and return the final result as an irreducible fraction string.

If the result is an integer, we still return it with denominator `1`.

For example:

```text
2
```

must be returned as:

```text
"2/1"
```

The input contains only digits, `/`, `+`, and `-`. Each input fraction is valid and irreducible. Each numerator and denominator is in the range `[1, 10]`, and the number of fractions is in the range `[1, 10]`. The final numerator and denominator fit in a 32-bit integer.

## Input and Output

| Item | Meaning |
|---|---|
| `expression` | String containing fraction addition and subtraction |
| Output | Reduced fraction as a string |
| Integer result | Returned with denominator `1` |

Example function shape:

```python
def fractionAddition(expression: str) -> str:
    ...
```

## Examples

Example 1:

```python
expression = "-1/2+1/2"
```

Output:

```python
"0/1"
```

The two fractions cancel each other.

Example 2:

```python
expression = "-1/2+1/2+1/3"
```

Output:

```python
"1/3"
```

The first two terms become `0`, so the final answer is `1/3`.

Example 3:

```python
expression = "1/3-1/2"
```

Output:

```python
"-1/6"
```

We compute:

```text
1/3 - 1/2 = 2/6 - 3/6 = -1/6
```

Example 4:

```python
expression = "5/3+1/3"
```

Output:

```python
"2/1"
```

The sum is `6/3`, which reduces to `2/1`.

## First Thought: Convert to Floating Point

A tempting solution is to convert each fraction to a decimal number and add them.

For example:

```python
1 / 3 - 1 / 2
```

But floating point arithmetic can introduce rounding errors.

The problem asks for an exact fraction in reduced form. So we should keep the calculation as integer numerator and denominator values.

## Key Insight

We can maintain the current result as one fraction:

```text
num / den
```

Initially, the result is:

```text
0 / 1
```

When adding a new fraction:

```text
a / b
```

the new result is:

```text
num / den + a / b
= (num * b + a * den) / (den * b)
```

Then we reduce the fraction using `gcd`.

This avoids floating point arithmetic entirely.

## Parsing the Expression

We need to extract signed fractions from the string.

For example:

```python
expression = "-1/2+1/2+1/3"
```

should be parsed as:

```python
(-1, 2)
(1, 2)
(1, 3)
```

A simple way in Python is to use a regular expression:

```python
[+-]?\d+
```

This extracts all signed integers.

For:

```python
"-1/2+1/2+1/3"
```

it gives:

```python
[-1, 2, 1, 2, 1, 3]
```

Then we read them in pairs:

```python
numerator, denominator
```

## Algorithm

1. Extract all signed integers from `expression`.
2. Initialize:
   - `num = 0`
   - `den = 1`
3. For each fraction `(a, b)`:
   - Set `num = num * b + a * den`.
   - Set `den = den * b`.
   - Reduce both by their greatest common divisor.
4. Return `f"{num}/{den}"`.

## Correctness

The algorithm maintains this invariant: after processing the first `k` fractions, `num / den` is exactly the sum of those `k` fractions in reduced form.

Before processing any fraction, the sum is `0 / 1`, so the invariant holds.

Assume the invariant holds before processing a new fraction `a / b`. The sum of the previous result and the new fraction is:

```text
num / den + a / b
= (num * b + a * den) / (den * b)
```

The algorithm assigns exactly this new numerator and denominator. Dividing both by their greatest common divisor changes only the representation, not the rational value. Therefore, the invariant still holds after processing the new fraction.

After all fractions are processed, the invariant says that `num / den` is exactly the value of the whole expression. Since we reduce after every step, the final fraction is irreducible. Therefore, the returned string is correct.

## Complexity

Let:

```text
n = len(expression)
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We parse the expression and process each number once |
| Space | `O(n)` | The regex list stores extracted integers |

The number of fractions is small in the official constraints, but the linear bound is the natural parsing cost.

## Implementation

```python
import math
import re

class Solution:
    def fractionAddition(self, expression: str) -> str:
        values = list(map(int, re.findall(r"[+-]?\d+", expression)))

        num = 0
        den = 1

        for a, b in zip(values[0::2], values[1::2]):
            num = num * b + a * den
            den = den * b

            g = math.gcd(abs(num), den)
            num //= g
            den //= g

        return f"{num}/{den}"
```

## Code Explanation

This line extracts all signed integers:

```python
values = list(map(int, re.findall(r"[+-]?\d+", expression)))
```

For example:

```python
"-1/2+1/2"
```

becomes:

```python
[-1, 2, 1, 2]
```

The current result starts at zero:

```python
num = 0
den = 1
```

This loop reads numerator-denominator pairs:

```python
for a, b in zip(values[0::2], values[1::2]):
```

The addition formula is:

```python
num = num * b + a * den
den = den * b
```

Then we reduce:

```python
g = math.gcd(abs(num), den)
num //= g
den //= g
```

Using `abs(num)` avoids sign issues. The denominator stays positive because all input denominators are positive.

Finally:

```python
return f"{num}/{den}"
```

returns the exact reduced fraction.

## Manual Parser Alternative

We can also parse without regular expressions.

```python
import math

class Solution:
    def fractionAddition(self, expression: str) -> str:
        num = 0
        den = 1
        i = 0
        n = len(expression)

        while i < n:
            sign = 1

            if expression[i] == "+":
                i += 1
            elif expression[i] == "-":
                sign = -1
                i += 1

            numerator = 0
            while i < n and expression[i].isdigit():
                numerator = numerator * 10 + int(expression[i])
                i += 1

            numerator *= sign

            i += 1

            denominator = 0
            while i < n and expression[i].isdigit():
                denominator = denominator * 10 + int(expression[i])
                i += 1

            num = num * denominator + numerator * den
            den = den * denominator

            g = math.gcd(abs(num), den)
            num //= g
            den //= g

        return f"{num}/{den}"
```

This version makes the parsing logic explicit.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.fractionAddition("-1/2+1/2") == "0/1"
    assert s.fractionAddition("-1/2+1/2+1/3") == "1/3"
    assert s.fractionAddition("1/3-1/2") == "-1/6"
    assert s.fractionAddition("5/3+1/3") == "2/1"
    assert s.fractionAddition("1/10+1/10") == "1/5"
    assert s.fractionAddition("-1/3-1/3") == "-2/3"

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `"-1/2+1/2"` | Sum becomes zero |
| `"-1/2+1/2+1/3"` | Cancellation followed by another term |
| `"1/3-1/2"` | Negative final result |
| `"5/3+1/3"` | Integer result must be returned as `/1` |
| `"1/10+1/10"` | Reduction after addition |
| `"-1/3-1/3"` | Multiple negative terms |