Fraction Addition and Subtraction: Parsing and Reducing Fractions

May 20, 20265 min read

leetcodeproblemmediummathstrings

Fraction Addition and Subtraction is LeetCode problem 592. You are given a string expression containing fractions with addition and subtraction, like "-1/2+1/2+1/3". Your job is to compute the result and return it as an irreducible fraction in the format "numerator/denominator". If the answer is zero, return "0/1". The input always starts with a fraction (possibly negative), and every fraction's numerator and denominator are within [0, 10].

Parsing "-1/2+1/2+1/3": each fraction token is extracted, then accumulated left to right starting from 0/1. Final result: 1/3.

Why this problem matters

This problem is a nice blend of two fundamental skills: string parsing and fraction arithmetic. On the parsing side, you need to carefully extract signed numerators and denominators from a flat character stream, handling the minus sign at the start of the string as a special case. On the arithmetic side, you need to combine fractions with different denominators using cross-multiplication, then reduce with the greatest common divisor (GCD).

Fraction manipulation shows up more often than you might expect in coding interviews. Whether it is computing exact probabilities, handling rational number arithmetic, or simplifying expressions, the core pattern is always the same: find a common denominator, combine numerators, and reduce. Mastering this small loop pays dividends across many problems.

The GCD-based reduction step is especially worth internalizing. Python gives you math.gcd, but understanding why you divide both numerator and denominator by their GCD (and how that guarantees an irreducible fraction) is the deeper lesson. It also connects to problems about LCM, modular arithmetic, and number theory more broadly.

The approach

The idea is to walk through the expression character by character, parsing one fraction at a time, and accumulating the result into a running numerator and denominator. After each addition, you reduce the fraction by dividing both parts by their GCD.

from math import gcd

def fractionAddition(expression):
    num, den = 0, 1
    i, n = 0, len(expression)

    while i < n:
        sign = 1
        if expression[i] == '+' or expression[i] == '-':
            if expression[i] == '-':
                sign = -1
            i += 1

        j = i
        while j < n and expression[j].isdigit():
            j += 1
        curr_num = sign * int(expression[i:j])
        i = j + 1

        j = i
        while j < n and expression[j].isdigit():
            j += 1
        curr_den = int(expression[i:j])
        i = j

        num = num * curr_den + curr_num * den
        den = den * curr_den

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

    return f"{num}/{den}"

Here is what each section does:

Sign detection: Check whether the current character is + or -. If it is -, set the sign to -1. If the expression starts with a digit (no leading sign), the sign defaults to 1.
Numerator parsing: Scan forward while characters are digits, then convert the substring to an integer and apply the sign.
Skip the slash: Increment i past the / character.
Denominator parsing: Same digit-scanning loop for the denominator.
Cross-multiply and add: The formula num = num * curr_den + curr_num * den combines the running fraction with the new one using a common denominator of den * curr_den.
GCD reduction: Divide both num and den by their GCD so the fraction stays irreducible throughout.

Python's math.gcd returns a non-negative value, but it expects non-negative inputs in older versions. Always pass abs(num) to be safe. Also, gcd(0, x) returns x, which correctly handles the case where the running numerator becomes zero.

Practice this problem with spaced repetition

Step-by-step walkthrough

Let's trace through the expression "-1/2+1/2+1/3" to see exactly how the accumulator evolves at each step.

Step 1: Initialize accumulator to 0/1

We start with num=0, den=1. This is equivalent to 0 and acts as the identity for addition.

Step 2: Parse and add -1/2

num = 0*2 + (-1)*1 = -1, den = 1*2 = 2. GCD(1,2) = 1. Result: -1/2.

Step 3: Parse and add +1/2

num = (-1)*2 + 1*2 = 0, den = 2*2 = 4. GCD(0,4) = 4. Result: 0/1 (zero cancels).

Step 4: Parse and add +1/3

num = 0*3 + 1*1 = 1, den = 1*3 = 3. GCD(1,3) = 1. Final result: 1/3.

Notice how the fraction is reduced after every addition. This keeps the numbers small and prevents overflow, which matters in languages without arbitrary-precision integers.

Complexity analysis

Metric	Value	Why
Time	O(n)	We scan through each character of the expression exactly once. Parsing, cross-multiplication, and GCD are all constant-time per fraction since numerator and denominator values are bounded by 10.
Space	O(1)	We only store the running numerator and denominator, plus a few loop variables. No extra data structures needed.

Build your pattern library with CodeBricks

Edge cases to watch for

Leading negative sign: The expression "-1/2" starts with - and has no leading +. Your sign detection must handle the very first character.
Result is zero: If fractions cancel out completely (like "-1/2+1/2"), the result is "0/1". The GCD step naturally handles this since gcd(0, d) returns d, giving 0/d which simplifies to 0/1.
Single fraction: The input might be just "1/3" with no operators at all. The while loop processes it in one pass.
Negative result: The sign lives in the numerator. A result like "-1/6" is valid, but "1/-6" is not. The algorithm naturally keeps the denominator positive because all input denominators are positive and we only multiply them together.
Multi-digit numerators: Values go up to 10, so you need the digit-scanning loop rather than reading a single character.

The building blocks

This problem combines two patterns that appear frequently in interview problems:

Character-by-character parsing is the backbone of problems like Fraction to Recurring Decimal, where you simulate long division by processing digits one at a time. The skill of managing an index pointer i while scanning ahead with j is reusable across many string problems.

Arithmetic with GCD reduction is the core of any problem involving exact fractions or rational numbers. The cross-multiplication formula (a/b + c/d = (a*d + c*b) / (b*d)) followed by GCD reduction is a self-contained building block. You will see the same GCD pattern in problems like Multiply Strings and Add Strings, where keeping intermediate results tidy is essential.

From understanding to recall

Solving this problem once teaches you the mechanics of fraction parsing and accumulation. But the real value comes from being able to reproduce the approach weeks later, when you encounter a similar problem with different surface-level details. Can you remember the cross-multiplication formula? Do you recall to always reduce by GCD after each step?

Spaced repetition helps bridge that gap between understanding and recall. By revisiting this problem at increasing intervals, you train your brain to recognize the pattern (parse a stream of tokens, accumulate with a running value, normalize after each step) and reach for the right tool without hesitation. That recognition speed is what separates solid interview performance from scrambling to re-derive solutions under time pressure.

Fraction to Recurring Decimal - Long division simulation with cycle detection, another fraction arithmetic problem
Multiply Strings - Digit-by-digit arithmetic on string representations of numbers
Add Strings - Character-level addition with carry propagation

Try CodeBricks free