592.分?jǐn)?shù)加減運(yùn)算

https://leetcode.cn/problems/fraction-addition-and-subtraction/solution/by-qingfengpython-g1mn/

難度：中等

題目：

給定一個表示分?jǐn)?shù)加減運(yùn)算的字符串expression，你需要返回一個字符串形式的計算結(jié)果。

這個結(jié)果應(yīng)該是不可約分的分?jǐn)?shù)，即最簡分?jǐn)?shù)。如果最終結(jié)果是一個整數(shù)，例如2，你需要將它轉(zhuǎn)換成分?jǐn)?shù)形式，其分母為1。
所以在上述例子中, 2應(yīng)該被轉(zhuǎn)換為2/1。

提示:

• 輸入和輸出字符串只包含'0' 到'9'的數(shù)字，以及'/', '+' 和'-'。
• 輸入和輸出分?jǐn)?shù)格式均為±分子/分母。如果輸入的第一個分?jǐn)?shù)或者輸出的分?jǐn)?shù)是正數(shù)，則'+'會被省略掉。
• 輸入只包含合法的最簡分?jǐn)?shù)，每個分?jǐn)?shù)的分子與分母的范圍是[1,10]。如果分母是1，意味著這個分?jǐn)?shù)實(shí)際上是一個整數(shù)。
• 輸入的分?jǐn)?shù)個數(shù)范圍是 [1,10]。
• 最終結(jié)果的分子與分母保證是 32 位整數(shù)范圍內(nèi)的有效整數(shù)。

示例：

示例1:

輸入:expression= "-1/2+1/2"
輸出: "0/1"
示例 2:

輸入:expression= "-1/2+1/2+1/3"
輸出: "1/3"
示例 3:

輸入:expression= "1/3-1/2"
輸出: "-1/6"

分析

首先這道題的提示中已經(jīng)明確不許考慮異常用例的場景，那么就簡單很多了。
這里注意一個小細(xì)節(jié)，數(shù)字只有0-9，不會存在兩位數(shù)，使得難度進(jìn)一步降低。
下來考慮以下，我們該以什么方式分割這些表達(dá)式：

1. 表達(dá)式字符串是一個個的個位數(shù)除法公式
2. 除了除法以外只涉及+ 、 - 法兩個符號
3. 減法可以轉(zhuǎn)化為 (+)-的方式，比如 -10 == (+)-10
4. 那么我們使用replace將所有-號轉(zhuǎn)化為+-
5. 再通過+號即可分割所有個位的除法公式

通過上述思路已經(jīng)將表達(dá)式分割成單個的除法，下來該怎么做？

既然最終仍要表達(dá)仍需要分式結(jié)尾，那么可以通過求所有分母的最小公倍數(shù)，然后將每個分子等比放大求和。
最終將分子總和與分母的最小公倍數(shù)，求最大公約數(shù)(即分子、分母約分)，返回答案即可。

解題：

Python:

from math import gcd
class Solution:
    def fractionAddition(self, expression: str) -> str:
        stack = [list(map(int, i.split('/'))) for i in expression.replace('-', '+-').split('+') if i]
        mod, total = 1, 0
        for i in stack:
            mod *= i[1] // gcd(mod, i[1])
        for i in stack:
            total += mod // i[1] * i[0]
        return '%s/%s' % (total // gcd(total, mod), mod // gcd(total, mod))

歡迎關(guān)注我的公_眾號: 清風(fēng)Python，帶你每日學(xué)習(xí)Python算法刷題的同時，了解更多python小知識。

我的個人博客：https://qingfengpython.cn

力扣解題合集：https://github.com/BreezePython/AlgorithmMarkdown