1.题目基本信息

1.1.题目描述

给定一个表示分数加减运算的字符串 expression ，你需要返回一个字符串形式的计算结果。

这个结果应该是不可约分的分数，即 最简分数。 如果最终结果是一个整数，例如 2，你需要将它转换成分数形式，其分母为 1。所以在上述例子中, 2 应该被转换为 2/1。

1.2.题目地址

https://leetcode.cn/problems/fraction-addition-and-subtraction/description/

2.解题方法

2.1.解题思路

配对匹配，求最小公倍数和最大公因数（最小公倍数=a*b//gcd(a,b)）

2.2.解题步骤

第一步，匹配(分子,分母)的对

第二步，构建函数combine，实现合并两个分数

第三步，遍历pairs构建分数

3.解题代码

python代码

def gcd(a:int, b:int) -> int:
    minVal, maxVal = min(a, b), max(a, b)
    r = maxVal % minVal
    while r != 0:
        maxVal = minVal
        minVal = r
        r = maxVal % minVal
    return minVal

class Solution:
    def fractionAddition(self, expression: str) -> str:
        # 思路：配对匹配，求最小公倍数和最大公因数（最小公倍数=a*b//gcd(a,b)）
        n = len(expression)
        # 第一步，匹配(分子,分母)的对
        pairs = []
        i = 0
        while i < n:
            # 匹配被除数
            sign = 1
            if expression[i] == "-":
                sign = -1
                i += 1
            elif expression[i] == "+":
                i += 1
            num1 = 0
            while expression[i].isdigit():
                num1 = num1 * 10 + int(expression[i])
                i += 1
            # 匹配除号
            i += 1
            # 匹配除数
            num2 = 0
            while i < n and expression[i].isdigit():
                num2 = num2 * 10 + int(expression[i])
                i += 1
            pairs.append((num1 * sign, num2))
        # print(pairs)
        # 第二步，构建函数combine，实现合并两个分数
        def combine(pair1, pair2):
            gcdVal = gcd(pair1[1], pair2[1])
            lcm = pair1[1] * pair2[1] // gcdVal # 分母的最小公倍数
            numerator = pair1[0] * (lcm // pair1[1]) + pair2[0] * (lcm // pair2[1])
            if numerator == 0:
                return (0, 1)
            gcd2 = gcd(abs(numerator), lcm)
            return (numerator // gcd2, lcm // gcd2)
        # 第三步，遍历pairs构建分数
        pair = pairs[0]
        for i in range(1, len(pairs)):
            pair = combine(pair, pairs[i])
        # print("pair", pair)
        return f"{pair[0]}/{pair[1]}"

4.执行结果