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:

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:

2

must be returned as:

"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

Example function shape:

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

Examples

Example 1:

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

Output:

"0/1"

The two fractions cancel each other.

Example 2:

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

Output:

"1/3"

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

Example 3:

expression = "1/3-1/2"

Output:

"-1/6"

We compute:

1/3 - 1/2 = 2/6 - 3/6 = -1/6

Example 4:

expression = "5/3+1/3"

Output:

"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:

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:

num / den

Initially, the result is:

0 / 1

When adding a new fraction:

a / b

the new result is:

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:

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

should be parsed as:

(-1, 2)
(1, 2)
(1, 3)

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

[+-]?\d+

This extracts all signed integers.

For:

"-1/2+1/2+1/3"

it gives:

[-1, 2, 1, 2, 1, 3]

Then we read them in pairs:

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:

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:

n = len(expression)

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

Implementation

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:

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

For example:

"-1/2+1/2"

becomes:

[-1, 2, 1, 2]

The current result starts at zero:

num = 0
den = 1

This loop reads numerator-denominator pairs:

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

The addition formula is:

num = num * b + a * den
den = den * b

Then we reduce:

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:

return f"{num}/{den}"

returns the exact reduced fraction.

Manual Parser Alternative

We can also parse without regular expressions.

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

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: