592.分?jǐn)?shù)加減運(yùn)算
https://leetcode.cn/problems/fraction-addition-and-subtraction/solution/by-qingfengpython-g1mn/
難度：中等
題目：
給定一個(gè)表示分?jǐn)?shù)加減運(yùn)算的字符串expression，你需要返回一個(gè)字符串形式的計(jì)算結(jié)果讳推。
這個(gè)結(jié)果應(yīng)該是不可約分的分?jǐn)?shù)顶籽，即最簡分?jǐn)?shù)。如果最終結(jié)果是一個(gè)整數(shù)银觅，例如2礼饱，你需要將它轉(zhuǎn)換成分?jǐn)?shù)形式，其分母為1。
所以在上述例子中, 2應(yīng)該被轉(zhuǎn)換為2/1镊绪。
提示:
- 輸入和輸出字符串只包含'0' 到'9'的數(shù)字匀伏，以及'/', '+' 和'-'。
- 輸入和輸出分?jǐn)?shù)格式均為±分子/分母蝴韭。如果輸入的第一個(gè)分?jǐn)?shù)或者輸出的分?jǐn)?shù)是正數(shù)够颠，則'+'會(huì)被省略掉。
- 輸入只包含合法的最簡分?jǐn)?shù)榄鉴，每個(gè)分?jǐn)?shù)的分子與分母的范圍是[1,10]履磨。如果分母是1，意味著這個(gè)分?jǐn)?shù)實(shí)際上是一個(gè)整數(shù)庆尘。
- 輸入的分?jǐn)?shù)個(gè)數(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)明確不許考慮異常用例的場景驶忌，那么就簡單很多了矛辕。
這里注意一個(gè)小細(xì)節(jié)，數(shù)字只有0-9付魔，不會(huì)存在兩位數(shù)聊品，使得難度進(jìn)一步降低。
下來考慮以下抒抬，我們該以什么方式分割這些表達(dá)式：
- 表達(dá)式字符串是一個(gè)個(gè)的個(gè)位數(shù)除法公式
- 除了除法以外只涉及+ 杨刨、 - 法兩個(gè)符號(hào)
- 減法可以轉(zhuǎn)化為 (+)-的方式，比如 -10 == (+)-10
- 那么我們使用replace將所有-號(hào)轉(zhuǎn)化為+-
- 再通過+號(hào)即可分割所有個(gè)位的除法公式
通過上述思路已經(jīng)將表達(dá)式分割成單個(gè)的除法擦剑，下來該怎么做妖胀？
既然最終仍要表達(dá)仍需要分式結(jié)尾，那么可以通過求所有分母的最小公倍數(shù)惠勒，然后將每個(gè)分子等比放大求和赚抡。
最終將分子總和與分母的最小公倍數(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)注我的公_眾號(hào): 清風(fēng)Python售担，帶你每日學(xué)習(xí)Python算法刷題的同時(shí)赁遗，了解更多python小知識(shí)。
我的個(gè)人博客：https://qingfengpython.cn
