Fraction Addition and Subtraction

Problem Statement

The task is to take a string input named expression that describes a mathematical operation involving the addition and subtraction of fractions and possibly integers represented as fractions (e.g., 2 expressed as 2/1). This string should then be processed to perform the described operations and produce a result, which will also be a string. The resultant fraction should be simplified to its irreducible form, meaning no further reduction is possible. If the result is an integer, it should be formatted as a fraction with the integer as the numerator and 1 as the denominator.

Examples

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"

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.

Approach and Intuition

To solve the problem laid out in the problem statement, follow these high-level steps:

1. Parsing the Input Expression:
   Start by extracting each fraction from the given expression string. Since the fractions are guaranteed to be correctly formatted and only contain valid characters ([0-9], /, +, -), they can be directly processed using regular expressions or string splitting techniques.

2. Fraction Operations:
   Calculate the result of the series of additions and subtractions by iterating over the extracted fraction elements. Implement handling for both operations:

   • Addition of Fractions: To add fractions, adjust both to a common denominator (typically the product of their denominators), sum the adjusted numerators, and keep the common denominator.
   • Subtraction of Fractions: This is similar to addition, except subtract the second numerator from the first after adjusting for a common denominator.

3. Simplifying the Result: Once the combined fraction is obtained, simplify it by dividing both the numerator and the denominator by their greatest common divisor (GCD). This ensures the result is in its irreducible form.

4. Formatting the Result:
   If the resulting fraction has a denominator of 1, then represent it as mentioned in the problem statement, with the format of numerator/1.

5. Edge Cases:
   Handle special cases like:

   • Operations result in a negative fraction.
   • The fraction reduces to zero (result should be 0/1).

By following these steps, each fraction operation can be computed efficiently and systematically, while ensuring the mathematical correctness and the specific format requirements as per the problem constraints.

Solutions

class Solution {
public:
    string fractionSum(string fracExp) {
        int numerator = 0;
        int denominator = 1;
    
        // Divide expression into individual fractions
        vector<string> fractionParts;
        int start = 0;
        if (fracExp[0] != '-') fracExp = '+' + fracExp;
        while (start < fracExp.size()) {
            int end = start + 1;
            while (end < fracExp.size() && fracExp[end] != '+' && fracExp[end] != '-') {
                end++;
            }
            fractionParts.push_back(fracExp.substr(start, end - start));
            start = end;
        }
    
        for (string frac : fractionParts) {
            size_t divider = frac.find('/');
            int numeratorPart = stoi(frac.substr(1, divider - 1));
            if (frac[0] == '-') numeratorPart *= -1;
            int denominatorPart = stoi(frac.substr(divider + 1));
    
            numerator = numerator * denominatorPart + numeratorPart * denominator;
            denominator = denominator * denominatorPart;
    
            int commonDivisor = abs(calculateGCD(numerator, denominator));
    
            numerator /= commonDivisor;
            denominator /= commonDivisor;
        }
    
        return to_string(numerator) + "/" + to_string(denominator);
    }
    
private:
    int calculateGCD(int x, int y) {
        if (x == 0) return y;
        return calculateGCD(y % x, x);
    }
};