Code Implementation

import re
from math import gcd

class Solution:
    def fractionAddition(self, expression: str) -> str:
        # Find all fractions in the expression
        tokens = re.findall(r'[+-]?\d+/\d+', expression)
        numerator, denominator = 0, 1

        for frac in tokens:
            n, d = map(int, frac.split('/'))
            # Add current fraction to the result
            numerator = numerator * d + n * denominator
            denominator *= d
            # Simplify after every addition
            g = gcd(abs(numerator), abs(denominator))
            numerator //= g
            denominator //= g

        # If denominator is negative, make it positive and flip sign
        if denominator < 0:
            numerator = -numerator
            denominator = -denominator

        return f"{numerator}/{denominator}"
      

#include <string>
#include <vector>
#include <sstream>
#include <numeric>
using namespace std;

class Solution {
public:
    string fractionAddition(string expression) {
        vector<string> tokens;
        int i = 0, n = expression.size();
        while (i < n) {
            int j = i + 1;
            while (j < n && expression[j] != '+' && expression[j] != '-') ++j;
            tokens.push_back(expression.substr(i, j - i));
            i = j;
        }
        int numerator = 0, denominator = 1;
        for (const string& frac : tokens) {
            int n, d;
            sscanf(frac.c_str(), "%d/%d", &n, &d);
            numerator = numerator * d + n * denominator;
            denominator *= d;
            int g = gcd(abs(numerator), abs(denominator));
            numerator /= g;
            denominator /= g;
        }
        if (denominator < 0) {
            numerator = -numerator;
            denominator = -denominator;
        }
        return to_string(numerator) + "/" + to_string(denominator);
    }
};
      

import java.util.*;
class Solution {
    public String fractionAddition(String expression) {
        List<String> tokens = new ArrayList<>();
        int i = 0, n = expression.length();
        while (i < n) {
            int j = i + 1;
            while (j < n && expression.charAt(j) != '+' && expression.charAt(j) != '-') j++;
            tokens.add(expression.substring(i, j));
            i = j;
        }
        int numerator = 0, denominator = 1;
        for (String frac : tokens) {
            String[] parts = frac.split("/");
            int n1 = Integer.parseInt(parts[0]);
            int d1 = Integer.parseInt(parts[1]);
            numerator = numerator * d1 + n1 * denominator;
            denominator *= d1;
            int g = gcd(Math.abs(numerator), Math.abs(denominator));
            numerator /= g;
            denominator /= g;
        }
        if (denominator < 0) {
            numerator = -numerator;
            denominator = -denominator;
        }
        return numerator + "/" + denominator;
    }
    private int gcd(int a, int b) {
        while (b != 0) {
            int tmp = a % b;
            a = b;
            b = tmp;
        }
        return a;
    }
}
      

var fractionAddition = function(expression) {
    let tokens = expression.match(/[+-]?\d+\/\d+/g);
    let numerator = 0, denominator = 1;

    function gcd(a, b) {
        if (!b) return a;
        return gcd(b, a % b);
    }

    for (let frac of tokens) {
        let [n, d] = frac.split('/').map(Number);
        numerator = numerator * d + n * denominator;
        denominator *= d;
        let g = Math.abs(gcd(numerator, denominator));
        numerator /= g;
        denominator /= g;
    }
    if (denominator < 0) {
        numerator = -numerator;
        denominator = -denominator;
    }
    return numerator + "/" + denominator;
};
      

Problem Description

You are given a string expression representing a mathematical expression involving the addition and subtraction of fractions (e.g., "-1/2+1/2+1/3"). Each fraction is represented as numerator/denominator and the expression may include both positive and negative fractions, separated by '+' and '-' signs. Your task is to compute the result of the expression and return it as a string in the form "numerator/denominator", where the numerator and denominator are reduced to their simplest form (i.e., the greatest common divisor of numerator and denominator is 1, and the denominator is always positive).

• There is exactly one valid answer for each input.
• The input string is always valid and non-empty.
• Fractions are separated only by '+' or '-' signs.
• Do not reuse or reorder the input fractions; process them in order.

Thought Process

The core challenge in this problem is to systematically parse and process a string that represents a sequence of fraction additions and subtractions. At first, one might think to split the string by operators and process each fraction, but handling signs and ensuring correct parsing can be tricky, especially with negative fractions or consecutive operations.

A brute-force approach would be to convert each fraction to a floating-point number, sum them, and then convert the result back to a fraction. However, this may lead to precision errors, and the problem specifically requires the answer in reduced fractional form.

Therefore, a better approach is to:

• Parse each fraction with its sign directly from the string.
• Maintain a running result as a numerator and denominator pair.
• Add each new fraction to the result using integer arithmetic.
• Simplify the result after each addition or subtraction by dividing both numerator and denominator by their greatest common divisor (GCD).

Solution Approach

Let's break down the algorithm step by step:

1. Tokenize the Expression:
   • Use a regular expression (or manual parsing) to split the input string into individual fractions, each with its sign.
   • This ensures we correctly handle both '+' and '-' operators and negative numbers.
2. Initialize Result:
   • Start with a running numerator and denominator, initially set to 0/1 (i.e., zero).
3. Process Each Fraction:
   • For each parsed fraction, extract its numerator and denominator.
   • Add it to the running result using the formula for adding fractions: a/b + c/d = (a*d + c*b) / (b*d).
   • After each operation, simplify the resulting fraction by dividing both numerator and denominator by their GCD.
4. Normalize the Result:
   • If the denominator is negative, multiply both numerator and denominator by -1 to ensure the denominator is positive.
5. Return the Result:
   • Format the final numerator and denominator as a string "numerator/denominator".

By always reducing the fraction at each step, we avoid integer overflow and ensure correctness.

Example Walkthrough

Let's walk through an example with the input expression = "-1/2+1/2+1/3":

1. Tokenize:
   • Tokens: ["-1/2", "+1/2", "+1/3"]
2. Initialize:
   • numerator = 0, denominator = 1
3. Process "-1/2":
   • n = -1, d = 2
   • New numerator = 0 * 2 + (-1) * 1 = -1
   • New denominator = 1 * 2 = 2
   • Simplify: GCD(-1, 2) = 1, so result = -1/2
4. Process "+1/2":
   • n = 1, d = 2
   • New numerator = -1 * 2 + 1 * 2 = 0
   • New denominator = 2 * 2 = 4
   • Simplify: GCD(0, 4) = 4, so result = 0/1
5. Process "+1/3":
   • n = 1, d = 3
   • New numerator = 0 * 3 + 1 * 1 = 1
   • New denominator = 1 * 3 = 3
   • Simplify: GCD(1, 3) = 1, so result = 1/3
6. Final Output:
   • Return "1/3"

Time and Space Complexity

Brute-force Approach:

• If we used floating-point arithmetic, parsing and summing would be O(n), but converting back to reduced fraction form would be tricky and potentially inaccurate.

• Time Complexity: O(k), where k is the number of fractions in the input. Each addition and GCD operation is constant time (since numerators and denominators are small, typically within 32-bit integer range).
• Space Complexity: O(k) for storing the list of tokens. All other variables use constant space.

The regular expression or manual parsing is linear in the length of the string, and the arithmetic operations are efficient.

Summary

The problem requires adding and subtracting fractions represented as a string and returning the result in reduced form. The key insight is to parse each fraction with its sign, use integer arithmetic to avoid floating-point errors, and reduce the result at every step using the greatest common divisor. This approach is efficient, accurate, and ensures the answer is always in the correct format. The solution elegantly combines careful string parsing with fundamental arithmetic operations, demonstrating a practical application of number theory in programming.