592. Fraction Addition and Subtraction
## 思路
n1/d1 +n2/d2 -n3/d3 = (n1/d1) + (n2/d2) + (-n3/d3)
(n1/d1) + (n2/d2) = (n1*d2 + n2*d1) / (d1 * d2)
先parse每個fraction pair並做相加,
最後再把分子分母除gcd
## Code
```python
class Solution:
def fractionAddition(self, expression: str) -> str:
n = len(expression)
i = 0
def get_num():
nonlocal i
is_neg = False
if expression[i] == '+':
i += 1
if expression[i] == '-':
is_neg = True
i += 1
num = 0
while i < n and expression[i].isdigit():
num = num * 10 + int(expression[i])
i += 1
return -num if is_neg else num
def get_gcd(a, b):
while b:
a, b = b, a % b
return a
curr_num, curr_deno = 0, 1
while i < n:
num = get_num()
i += 1 # `/`
deno = get_num()
# (n1/d1) + (n2/d2) = (n1*d2 + n2*d1) / (d1 * d2)
curr_num = curr_num * deno + num * curr_deno
curr_deno = curr_deno * deno
if curr_num == 0:
return '0/1'
gcd = get_gcd(curr_num, curr_deno)
return f'{curr_num//gcd}/{curr_deno//gcd}'
```