Beats 100% users in C++.
Intuition\nThe problem involves adding and subtracting fractions from an expression. Fractions consist of a numerator and a denominator, and to perform addition
# Intuition\nThe problem involves adding and subtracting fractions from an expression. Fractions consist of a numerator and a denominator, and to perform addition or subtraction, we can use the common denominator method. After performing operations on the fractions, we reduce the resulting fraction to its simplest form by dividing both the numerator and denominator by their greatest common divisor (GCD).\n\n![Screenshot from 2024-09-10 17-28-38.png](https://assets.leetcode.com/users/images/8d11ebfc-6027-46d3-b944-30d2f5e4ca9e_1725969524.1092923.png)\n\n# Approach\n1. Parse each fraction from the input string. A fraction has the form `a/b`, where `a` is the numerator and `b` is the denominator.\n2. Identify the sign (`+` or `-`) before each fraction to determine whether it should be added or subtracted.\n3. Use the formula for adding/subtracting fractions with different denominators:  \n   $$ \\frac{a}{b} \\pm \\frac{c}{d} = \\frac{a \\cdot d \\pm c \\cdot b}{b \\cdot d} $$\n4. After each operation, reduce the resulting fraction by dividing both the numerator and denominator by their GCD.\n5. Ensure the denominator is positive. If the denominator is negative, multiply both the numerator and denominator by `-1` to keep the denominator positive.\n6. Finally, return the resulting fraction in string format as `"numerator/denominator"`.\n\n# Complexity\n- **Time complexity:**  \n  Parsing the expression involves scanning each character, resulting in a complexity of $$O(n)$$, where $$n$$ is the length of the input string. Each GCD operation takes $$O(\\log(\\min(a,b)))$$, but this is dominated by the linear scan.\n\n- **Space complexity:**  \n  The space complexity is $$O(1)$$, as the space used is constant, not dependent on the input size.\n\n# Code\n```cpp\nclass Solution {\npublic:\n    // Helper function to reduce the fraction by its GCD\n    void reduceFraction(int& numerator, int &denominator)\n    {\n        int greatestCommonDivisor = __gcd(numerator, denominator);\n        numerator /= greatestCommonDivisor;\n        denominator /= greatestCommonDivisor;\n        // Ensure the denominator is positive\n        if(denominator < 0)\n        {\n            numerator *= -1;\n            denominator *= -1;\n        }\n    }\n    \n    // Function to process the fraction addition expression\n    string fractionAddition(string expression) {\n        int numerator = 0; // Initialize numerator to 0\n        int denominator = 1; // Initialize denominator to 1 (for a valid fraction)\n        bool positiveFlag = true; // To track the sign of each fraction\n        \n        // Loop through the input expression\n        for(int index = 0 ; index < expression.length() ; )\n        {\n            // Check for numbers in the expression (i.e., the numerator)\n            if(expression[index] >= \'0\' && expression[index] <= \'9\')\n            {\n                int currNumerator = 0;\n                // Parse the numerator of the fraction\n                while(expression[index] != \'/\') {\n                    currNumerator = 10 * currNumerator + (expression[index] - \'0\');\n                    index++;\n                }\n                index++; // Skip the \'/\'\n                \n                // Parse the denominator of the fraction\n                int currDenominator = 0;\n                while(expression[index] >= \'0\' && expression[index] <= \'9\') {\n                    currDenominator = 10 * currDenominator + (expression[index] - \'0\');\n                    index++;\n                }\n                \n                // Update the numerator and denominator based on the current fraction\n                if(positiveFlag) {\n                    numerator = numerator * currDenominator + currNumerator * denominator;\n                } else {\n                    numerator = numerator * currDenominator - currNumerator * denominator;\n                }\n                denominator *= currDenominator;\n                \n                // Reduce the fraction to its simplest form\n                reduceFraction(numerator, denominator);\n            }\n            else {\n                // Handle signs in the expression\n                if(expression[index] == \'+\')\n                    positiveFlag = true;\n                else\n                    positiveFlag = false;\n                index++;\n            }\n        }\n        \n        // Return the final reduced fraction in string format\n        return to_string(numerator) + \'/\' + to_string(denominator);\n    }\n};\n
['C++']