Problem statement

https://leetcode.com/problems/fraction-addition-and-subtraction/

Solution

Split string into fractions, we can do it using regular expressions for example. Then split every fraction and put into s pairs of numerator/denominator. Then use function AddFrac and traverse our list, adding fractions one by one.

Complexity

Space complexity is O(n), time complexity is O(n log x), where x is the biggest possible value of denominator, because we use gcd function. We can also first sum all fraction and then use gcd only once but for bigger numbers.

Code

class Solution:
    def fractionAddition(self, expression):
        def AddFrac(a,b,c,d):
            m, n = a*d+b*c, b*d
            Q = math.gcd(m,n)
            return [m//Q, n//Q]
        
        if expression[0] != "-" : expression = "+" + expression
        fractions = re.split("[+-]+", expression)[1:]
        signs = [int(s=="+")*2-1 for s in expression if s in "+-"]
        n = len(signs)
        
        s = []
        for i in range(n):
            a, b = fractions[i].split("/")
            s.append([int(a)*signs[i], int(b)])
            
        while len(s) > 1:
            a, b = s.pop()
            c, d = s.pop()
            s.append(AddFrac(a,b,c,d))
            
        return str(s[0][0]) + "/" + str(s[0][1])