Solution Explanation

This problem involves adding and subtracting fractions represented as strings. The challenge lies in efficiently handling the string parsing and fraction arithmetic, and then simplifying the final result to an irreducible fraction.

The core idea behind the solution is to use a least common multiple (LCM) approach to avoid dealing with fractions directly until the very end. The solution leverages the fact that the denominators are relatively small (between 1 and 10). Instead of finding the LCM for every pair of fractions, a large enough common denominator is pre-computed which will always be divisible by all potential denominators (from 1 to 10). The choice of 6 * 7 * 8 * 9 * 10 as the common denominator (y in the code) guarantees that all possible denominators will divide into it.

Here's a breakdown of the solution:

1. Preprocessing:

   • The input string expression is checked and a + sign is prepended if it starts with a digit, ensuring consistent handling of signs.
   • A common denominator y (678910) is initialized. This simplifies the calculations by avoiding explicit LCM computations at each step.
   • The numerator x is initialized to 0.

2. Iterating through Fractions:

   • The code iterates through the expression using a while loop. Each iteration processes a single fraction:
   • Sign Handling: The sign (+ or -) of the fraction is extracted.
   • Fraction Extraction: The numerator and denominator of the fraction are parsed from the string using string manipulation.
   • Numerator Update: The numerator x is updated by adding the contribution of the current fraction. The formula x += sign * int(a) * y // int(b) converts the fraction to a representation with the common denominator y and adds it to the running sum x.

3. Simplifying the Result:

   • After processing all fractions, the result is a fraction x/y. To simplify this to an irreducible fraction, the greatest common divisor (GCD) of x and y is calculated using Euclid's algorithm (gcd function).
   • Both x and y are divided by the GCD to obtain the final irreducible fraction.

4. Output:

   • The final irreducible fraction is formatted as a string "x/y" and returned.

Time and Space Complexity Analysis

• Time Complexity: O(n), where n is the length of the input string. The loop iterates through the string once to parse and process each fraction. The GCD calculation takes O(log min(x, y)) time which is dominated by the string processing time.

• Space Complexity: O(1). The solution uses a constant amount of extra space regardless of the input size. The intermediate variables used to store numerators, denominators, and the results are all of fixed size, not dependent on the input string's length.

Code in Different Languages (as requested)

The code implementations in Python, Java, Go, and JavaScript provided earlier in the response follow this algorithm precisely. Each demonstrates the same fundamental approach, adapted to the specifics of each language's syntax and standard libraries. The GCD function is a common component used in all the languages.