Fraction Arithmetic with Simplification: Parsing, Common Denominators, and GCD Reduction
Intuition\n Describe your first thoughts on how to solve this problem. \nWhen dealing with fraction addition and subtraction, we need to carefully manage the ar
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWhen dealing with fraction addition and subtraction, we need to carefully manage the arithmetic operations between fractions, which involve finding a common denominator and simplifying the result. The key challenge is to parse the expression correctly, handle the signs, and ensure that the final fraction is reduced to its simplest form. By iterating through the expression, we can sequentially process each fraction, accumulating the result while maintaining the correct sign and simplifying as we go.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1.Parsing the Expression: Iterate through the input string to extract each fraction. Identify the sign (+ or -) and then extract the numerator and denominator of the fraction.\n\n2.Common Denominator: To add or subtract fractions, convert them to a common denominator. This is done by adjusting the numerator of each fraction accordingly.\n\n3.Updating the Result: Maintain a running total of the result as a fraction by adding or subtracting the adjusted numerators. The denominator remains the common one.\n\n4.Simplification: After each operation, simplify the fraction by finding the greatest common divisor (GCD) of the numerator and denominator, and divide both by this GCD.\n\n5.Final Output: Return the result in the format numerator/denominator, ensuring that even if the result is an integer, it is expressed as a fraction (e.g., 2 becomes 2/1).\n\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```java []\nclass Solution {\n    public String fractionAddition(String expression) {\n        int numerator = 0, denominator = 1;\n        int i = 0, n = expression.length();\n\n        while (i < n) {\n            // Read the numerator\n            int sign = 1;\n            if (expression.charAt(i) == \'-\' || expression.charAt(i)==\'+\'){\n                sign = expression.charAt(i) == \'-\' ? -1 : 1;\n                i++;\n            }\n\n            int num = 0;\n            while (i < n && Character.isDigit(expression.charAt(i))) {\n                num = num * 10 + (expression.charAt(i) - \'0\');\n                i++;\n            }\n            num *= sign;\n            i++;\n\n            // Read the denominator\n            int den = 0;\n            while (i < n && Character.isDigit(expression.charAt(i))) {\n                den = den * 10 + (expression.charAt(i) - \'0\');\n                i++;\n            }\n\n            // Add the fraction to the result\n            numerator = numerator * den + num * denominator;\n            denominator *= den;\n\n            // Simplify the fraction\n            int gcd = gcd(Math.abs(numerator), denominator);\n            numerator /= gcd;\n            denominator /= gcd;\n        }\n        return numerator + "/" + denominator;\n    }\n    // Helper function to compute the GCD (Greatest Common Divisor)\n    private static int gcd(int a, int b) {\n        while (b != 0) {\n            int temp = b;\n            b = a % b;\n            a = temp;\n        }\n        return a;\n    }\n}\n```
['Java']