592. Fraction Addition and Subtraction

Loading...LeetCode

# 整体逻辑是从前往后扫, 扫到符号就停下来, 用res = res(在此是res = 0/1)加exp[0:i]的数
# 接着从符号继续往后扫, 扫到第二个符号继续停下来, 继续相加.
# 相加的部分, 要先用/分割成分子和分母, 然后转成int, 再交叉相加.
# 加完之后, 要用gcd(最大公约数算法)找gcd.

# 另外可以看看这个OO的算法, 应该也很好:, 可以学习一下.
# https://leetcode.com/problems/fraction-addition-and-subtraction/discuss/313162/Python-object-oriented-solution-94-time-98-space-one-pass
class Solution:
    def fractionAddition(self, expression: str) -> str:
        def cal(num_a, num_b):
            def gcd(a, b):
                return b if a == 0 else gcd(b % a, a)
            tmp_a = num_a.split('/')
            tmp_b = num_b.split('/')
            lst_a = (int(tmp_a[0]),int(tmp_a[1]))
            lst_b = (int(tmp_b[0]),int(tmp_b[1]))
            numerator = lst_a[0] * lst_b[1] + lst_a[1] * lst_b[0]
            denominator = abs(lst_a[1]) * abs(lst_b[1])
            g = gcd(numerator, denominator)
            numerator //= g
            denominator //= g
            return ('-' if numerator * denominator < 0 else '') + str(abs(numerator)) + '/' + str(abs(denominator))
        
        res = '0/1'
        cur = 0
        i = 0
        
        while i < len(expression):
            c = expression[i]
            if c == '+' or c == '-' and i != 0:
                res = cal(res, expression[cur : i])
                cur = i
            i += 1
        return cal(res, expression[cur:])