Efficiently Adding Fractions: Parsing and Simplifying in One Pass
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem involves combining fractions from a string expression by parsing each fract
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem involves combining fractions from a string expression by parsing each fraction and then adding or subtracting them using a common denominator. As you process each fraction, you adjust the cumulative result by updating the numerator and denominator accordingly. Finally, simplify the result by reducing it to its simplest form using the greatest common divisor (GCD).\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe problem involves evaluating an expression composed of fractions connected by + or - signs, e.g., -1/2+1/3-1/4. The goal is to return the result in its simplest form as a fraction.\n\n1. Initialize Variable:\n    - `nume` (numerator) is initialized to `0`. This will hold the cumulative numerator as we process the fractions.\n    - `deno` (denominator) is initialized to `1`. This will hold the cumulative denominator as we process the fractions.\n    - `i` is the index for traversing the string, and `n` is the length of the input string.\n2. The main loop iterates through the entire expression string.\n3. Identify and Parse Each Fraction:\n    1. Sign Detection:\n        - Check if the current character is $$\'-\' or \'+\'$$. If it\'s $$\'-\'$$, set `isNeg` to $$true$$, indicating that the upcoming fraction will be negative.\n        - If the character is a sign, increment `i` to $$skip$$ it.\n    2. Parse Numerator:\n        - Build the numerator by iterating over the digits until you encounter the division character `\'/\'`. Convert the character digits to an integer (`curNum`).\n    3. Parse Denominator:\n        - Skip the division character and build the denominator by iterating over the digits after the `\'/\'`. Convert these digits into an integer (`curDen`).\n    4. Apply Sign:\n        - If the fraction is negative (`isNeg == true`), multiply curNum by $$-1$$.\n4. Update the Cumulative Fraction:\n    1. Use this formula to add fractions:\n        - `new\xA0numerator=nume X curDen + curNum X deno`\n        - `new\xA0denominator=deno\xD7curDen`\n    2. Update` nume` and `deno` with the new values.\n5. Simplify the Resulting Fraction:\n    - Compute the Greatest Common Divisor (`GCD`) of the numerator and denominator using the built-in $$__gcd function$$.\n    - Divide both the numerator and denominator by their GCD to reduce the fraction to its simplest form.\n6. Return the Result:\n    - Convert the simplified numerator and denominator to a string in the form `"nume/deno"` and return it.\n\n# Example Walkthrough\nConsider the expression $$-1/2+1/3-1/4$$:\n- Start with `nume = 0, deno = 1`.\n- Process $$-1/2$$:\n    - $$curNum = -1, curDen = 2$$.\n    - Update $$nume$$ = 0 * 2 + (-1) * 1 = -1.\n    - Update $$deno$$ = 1 * 2 = 2.\n- Process` +1/3`:\n    - $$curNum = 1, curDen = 3$$.\n    - Update $$nume$$ = -1 * 3 + 1 * 2 = -3 + 2 = -1.\n    - Update $$deno$$ = 2 * 3 = 6.\n- Process -1/4:\n    - $$curNum = -1, curDen = 4$$.\n    - Update $$nume$$ = -1 * 4 + (-1) * 6 = -4 + (-6) = -10.\n    - Update $$deno$$ = 6 * 4 = 24.\n- Simplify:\n    - $$GCD = 2$$.\n    - $$nume$$ = -10 / 2 = -5, $$deno$$ = 24 / 2 = 12.\n- `Result: "-5/12"`.\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    string fractionAddition(string expression) {\n        int nume = 0;\n        int deno = 1;\n\n        int i = 0;\n        int n = expression.size();\n        while(i < n){\n            int curNum = 0;\n            int curDen = 0;\n\n            bool isNeg = (expression[i] == \'-\');\n            \n            if(expression[i]== \'+\' || expression[i] == \'-\'){\n                i++;\n            }\n\n            // Build the currName\n            while(i < n && isdigit(expression[i])){\n                int val = expression[i] - \'0\';\n                curNum = (curNum*10) + val;\n                i++;\n            }\n\n            i++; // numerator / division // skiping the divisor character\n\n            if(isNeg == true) curNum *= -1;\n\n            // Build the currDeno\n            while(i < n && isdigit(expression[i])){\n                int val = expression[i] - \'0\';\n                curDen = (curDen*10) + val;\n                i++;\n            }\n\n            nume = nume * curDen + curNum * deno;\n            deno = deno * curDen;\n        }\n        int GCD = abs(__gcd(nume,deno));\n\n        // - 3 / 6 // GCD : 3\n        nume /= GCD;\n        deno /= GCD;\n        return to_string(nume) + "/" + to_string(deno);\n    }\n};\n```
['C++']