Сложность: medium
Дана строка, представляющая выражение сложения и вычитания дробей, верните результат вычисления в строковом формате.
Окончательный результат должен быть несократимой дробью. Если ваш окончательный результат является целым числом, преобразуйте его в формат дроби с знаменателем 1. Таким образом, 2 должно быть преобразовано в 2/1.
Пример:
Input: expression = "-1/2+1/2+1/3"
Output: "1/3"
👨💻 Алгоритм:
1⃣Начните сканирование строки и разделите её на части, содержащие числители и знаменатели, с учетом знаков.
2⃣Выполните операции сложения или вычитания для каждой пары дробей, приводя их к общему знаменателю и сокращая результат.
3⃣Верните результат в виде строки, представляющей несократимую дробь.
😎 Решение:
def gcd(a, b):
while b:
a, b = b, a % b
return a
class Solution:
def fractionAddition(self, expression: str) -> str:
sign = []
if expression[0] != '-':
sign.append('+')
for char in expression:
if char in '+-':
sign.append(char)
fractions = expression.replace('-', '+-').split('+')
prev_num, prev_den = 0, 1
i = 0
for sub in fractions:
if not sub:
continue
num, den = map(int, sub.split('/'))
g = gcd(prev_den, den)
if sign[i] == '+':
prev_num = prev_num * den // g + num * prev_den // g
else:
prev_num = prev_num * den // g - num * prev_den // g
prev_den = prev_den * den // g
g = abs(gcd(prev_num, prev_den))
prev_num //= g
prev_den //= g
i += 1
return f"{prev_num}/{prev_den}"
Ставь 👍 и забирай 📚 Базу знаний