Published 2024-08-22

0592. Fraction Addition and Subtraction

leetcode

Problem

You are given a string expression that represents a mathematical expression of fractions. The fractions are either separated by a plus sign (+) or a minus sign (-), and represent either positive or negative fractions. The task is to evaluate the expression and return the result as a string in the form of a reduced fraction.

Examples:

  • expression = "-1/2+1/2+1/3" returns "1/3"
  • expression = "1/3-1/2" returns "-1/6"
  • expression = "-1/2+1/2+1/3-1/3" returns "0/1"

Constraints:

  • The input string only contains '0-9', '/', '-', '+'.
  • The sign of every fraction is determined by the operators before it.
  • The result should be a reduced fraction in the form where the numerator and denominator have no common factors greater than 1.

Solution Description

To implement a solution for fraction addition and subtraction, we need to:

  1. Parse the string to extract the individual fractions along with their signs.
  2. For each fraction, convert it to a common denominator to make the addition/subtraction straightforward.
  3. Combine the fractions taking into account their signs.
  4. Reduce the result fraction by finding the greatest common divisor (GCD) of the numerator and denominator.
  5. Return the result as a string in the form numerator/denominator.

Example

Consider the input string "-1/2+1/2+1/3":

  1. Parse the string to get fractions: -1/2, 1/2, 1/3.
  2. Convert each fraction to a common denominator:
    • Common denominator for this example would be 6.
    • Converting fractions: -1/2 = -3/6, 1/2 = 3/6, 1/3 = 2/6.
  3. Perform the addition: -3/6 + 3/6 + 2/6 = 2/6.
  4. Reduce 2/6 by GCD of 2 and 6 which is 2:
    • Result: 2/6 = 1/3.
  5. Return the result: "1/3".

References

This problem requires understanding of the following:

  • Parsing strings in JavaScript.
  • Finding the least common multiple (LCM) and greatest common divisor (GCD).
  • Basic fraction addition and reduction.

Solution

Let's define a function to solve this problem and a series of test cases. 

/**
 * Main function to solve the problem of fraction addition and subtraction.
 * @param {string} expression - The input string representing the expression.
 * @returns {string} The result as a reduced fraction.
 */
function fractionAddition(expression) {
    // Log helpers
    const log = typeof NestedInteger !== 'undefined' ? () => {} : console.log;
    const table = typeof NestedInteger !== 'undefined' ? () => {} : console.table;

    /**
     * This function calculates the greatest common divisor of two numbers
     * @param {number} a
     * @param {number} b
     * @returns {number} greatest common divisor of a and b
     */
    function gcd(a, b) {
        log(`Calculating GCD of ${a} and ${b}`);
        return b === 0 ? a : gcd(b, a % b);
    }

    /**
     * This function computes the least common multiple of two numbers
     * @param {number} a
     * @param {number} b
     * @returns {number} least common multiple of a and b
     */
    function lcm(a, b) {
        return (a * b) / gcd(a, b)
    }



    function frac(sign, top, bot) {
        return { sign, top, bot };
    }


    function isPSign(ch) {
        return ch === '+';
    }

    function isNSign(ch) {
        return ch === '-';
    }


    /**
      *
      * @param {string} input
      * @returns { Object[] }
      */
    function parseFractions(input) {
        if (!input) return [];
        if (input.length < 3) throw `Invalid input '${input}'`

        const ret = [];
        let cur = frac(1, 0, 0);
        let start = 0;
        if (isPSign(input[0])) {
            cur.sign = 1;
            start = 1;
        } else if (isNSign(input[0])) {
            cur.sign = -1;
            start = 1;
        }

        let parseTop = true;

        for (let i = start; i < input.length; i++) {
            const ch = input[i];
            if (isPSign(ch) || isNSign(ch)) {
                ret.push(cur);
                cur = frac(0, 0, 0);
                cur.sign = isPSign(ch) ? 1 : -1;
                parseTop = true;
            } else if (ch === '/') {
                parseTop = false;
            } else {
                if (parseTop) {
                    cur.top = (cur.top * 10) + + ch;
                } else {
                    cur.bot = (cur.bot * 10) + + ch;
                }
            }
        }
        ret.push(cur);

        return ret;
    }

    const fractions = parseFractions(expression);
    log(`Expression = '${expression}'`);
    table(fractions);

    // find the least common denomiator
    let lcd = fractions[0].bot;
    for (let i = 1; i < fractions.length; i++) {
        lcd = lcm(lcd, fractions[i].bot);
    }
    log(`Least Common Denominator (LCD) = ${lcd}`);

    let numeratorSum = 0;
    for (const frac of fractions) {
        numeratorSum += frac.sign * frac.top * (lcd / frac.bot);
    }
    log(`Numerator Sum = ${numeratorSum}`);

    // finally
    const gcdFinal = gcd(Math.abs(numeratorSum), lcd);
    const finalNumerator = numeratorSum / gcdFinal;
    const finalDenominator = lcd / gcdFinal;

    return `${finalNumerator}/${finalDenominator}`;
}

// Test cases
const testCases = [
    { expression: "-1/2+1/2+1/3", expected: "1/3" },
    { expression: "1/3-1/2", expected: "-1/6" },
    { expression: "-1/2+1/2+1/3-1/3", expected: "0/1" },
    { expression: "5/3+1/3", expected: "2/1" },
    { expression: "-3/7+7/10-3/4", expected: "-41/140" },
    // Additional test cases to ensure comprehensive coverage.
];

testCases.forEach((test, index) => {
    const result = fractionAddition(test.expression);
    console.log(`Test Case ${index + 1}: ${result === test.expected ? 'Passed' : 'Failed'} (Expected: ${test.expected}, Got: ${result})`);
});

Remember to implement the actual logic inside the fractionAddition function.

© d)zharii. sitemap