[Kotlin] Irreducible Fractions: Parsing and Summation Techniques | 139ms
Intuition\nThe problem involves parsing a string representing an expression of fraction addition and subtraction, performing the addition, and then simplifying 
# Intuition\nThe problem involves parsing a string representing an expression of fraction addition and subtraction, performing the addition, and then simplifying the resulting fraction. The key challenge is to correctly handle both positive and negative fractions and to simplify the final fraction to its irreducible form.\n\n# Approach\n1. **Parsing Fractions:** To parse the expression, we iterate over each character in the expression. Whenever we encounter a \'+\' or \'-\' character, we split the expression at that point to extract the fraction. We then convert the substrings into integer pairs representing numerators and denominators.\n   \n2. **Adding Fractions:** Once we have parsed all the fractions, we need to add them up to get the sum. We iterate over the list of parsed fractions and accumulate the sum in two variables: numerator and denominator. We perform the addition by multiplying each fraction\'s numerator by the product of the denominators and adding it to the product of the denominators multiplied by the numerator.\n\n3. **Simplifying Fraction:** After obtaining the sum of all fractions, we need to simplify the resulting fraction. To do this, we find the greatest common divisor (GCD) of the numerator and denominator using the Euclidean algorithm. Then, we divide both the numerator and denominator by their GCD to obtain the simplified fraction.\n\n4. **Returning Result:** Finally, we return the simplified fraction as a string in the required format, ensuring that negative fractions are represented correctly and that the denominator is always positive.\n\nThis approach ensures that we correctly handle both positive and negative fractions, perform the addition accurately, and simplify the resulting fraction to its irreducible form.\n\n# Complexity\n- **Time complexity:** The time complexity of parsing the fractions, performing addition, and simplifying the fraction is linear, i.e., O(n), where n is the length of the given expression.\n  \n- **Space complexity:** The space complexity is also linear, O(n), where n is the number of fractions in the expression.\n\n# Code\n```\nclass Solution {\n    fun fractionAddition(expression: String): String {\n        val fractions = parseFractions(expression)\n        val result = addFractions(fractions)\n        return simplifyFraction(result)\n    }\n\n    private fun parseFractions(expression: String): List<Pair<Int, Int>> {\n        val fractions = mutableListOf<Pair<Int, Int>>()\n        var numerator = 0\n        var denominator = 0\n        var sign = 1\n        var number = ""\n\n        for (char in expression) {\n            when (char) {\n                \'+\', \'-\' -> {\n                    if (number.isNotEmpty()) {\n                        val fraction = number.split("/")\n                        numerator = sign * fraction[0].toInt()\n                        denominator = fraction[1].toInt()\n                        fractions.add(Pair(numerator, denominator))\n                    }\n                    sign = if (char == \'+\') 1 else -1\n                    number = ""\n                }\n                else -> number += char\n            }\n        }\n\n        if (number.isNotEmpty()) {\n            val fraction = number.split("/")\n            numerator = sign * fraction[0].toInt()\n            denominator = fraction[1].toInt()\n            fractions.add(Pair(numerator, denominator))\n        }\n\n        return fractions\n    }\n\n    private fun addFractions(fractions: List<Pair<Int, Int>>): Pair<Int, Int> {\n        var numerator = 0\n        var denominator = 1\n\n        for ((num, denom) in fractions) {\n            numerator = numerator * denom + num * denominator\n            denominator *= denom\n        }\n\n        return Pair(numerator, denominator)\n    }\n\n    private fun gcd(a: Int, b: Int): Int {\n        return if (b == 0) a else gcd(b, a % b)\n    }\n\n    private fun simplifyFraction(fraction: Pair<Int, Int>): String {\n        val numerator = fraction.first\n        val denominator = fraction.second\n\n        if (numerator == 0) return "0/1"\n        \n        val gcd = gcd(Math.abs(numerator), Math.abs(denominator))\n        val sign = if (numerator < 0 || denominator < 0) "-" else ""\n        \n        val simplifiedNumerator = Math.abs(numerator) / gcd\n        val simplifiedDenominator = Math.abs(denominator) / gcd\n\n        return "$sign$simplifiedNumerator/$simplifiedDenominator"\n    }\n}\n\n```
['Math', 'String', 'Simulation', 'Kotlin']