这个题解的思路是模拟分数加减运算的过程。首先定义了求最大公约数(gcd)和最小公倍数(lcm)的函数。然后定义了分数加法函数add,根据两个分数的分母是否相同来进行不同的处理。接着遍历给定的表达式,用一个临时变量 tmp 来记录当前处理的数字。遇到 '+' 或 '-' 时,根据前面的符号对当前分数进行加减运算,并更新符号。遇到 '/' 时,将当前数字作为分子,并切换到分母。最后,将表达式中最后一个分数也加入计算,并对结果进行约分。
时间复杂度: O(nlogM),其中 n 是表达式的长度,M 是分母的最大值。
空间复杂度: O(1)
class Solution:
def fractionAddition(self, expression: str) -> str:
def gcd(x,y):
while y:
x, y = y, x%y
return x
def lcm(x,y):
return (x*y)//gcd(x,y)
def add(num1, num2, sign):
if num1[1] == num2[1]:
return [num1[0]+sign*num2[0],num1[1]]
else:
cm = lcm(num1[1],num2[1])
return [num1[0]*(cm//num1[1]) + sign*num2[0]*(cm//num2[1]), cm]
tmp = ""
res = [0,1] # 存储最终结果
num = [0,1] # 存储当前处理的分数
sign = 1 # 当前的运算符号
idx = 0 # num中当前存储分子(0)还是分母(1)
for c in expression:
if c == '+' or c == '-':
if tmp != '': # 将当前分数加入结果
num[idx] = int(tmp)
tmp = ""
res = add(res, num, sign)
idx = 0
if c == '+': # 更新运算符号
sign = 1
else:
sign = -1
elif c == '/':
num[idx] = int(tmp) # 当前数字作为分子
idx = 1 - idx # 切换到分母
tmp = ""
else:
tmp += c # 记录当前数字
num[idx] = int(tmp) # 将最后一个分数加入结果
tmp = ""
res = add(res, num, sign)
cd = gcd(res[0], res[1]) # 结果约分
return "%d/%d" % (res[0]//cd, res[1]//cd)