Задача: 592. Fraction Addition and Subtraction
Сложность: medium

Дана строка, представляющая выражение сложения и вычитания дробей, верните результат вычисления в строковом формате.
Окончательный результат должен быть несократимой дробью. Если ваш окончательный результат является целым числом, преобразуйте его в формат дроби с знаменателем 1. Таким образом, 2 должно быть преобразовано в 2/1.

Пример:

Input: expression = "-1/2+1/2+1/3"
Output: "1/3"

👨‍💻 Алгоритм:

1⃣Начните сканирование строки и разделите её на части, содержащие числители и знаменатели, с учетом знаков.

2⃣Выполните операции сложения или вычитания для каждой пары дробей, приводя их к общему знаменателю и сокращая результат.

3⃣Верните результат в виде строки, представляющей несократимую дробь.

😎 Решение:

class Solution {
    function fractionAddition($expression) {
        $sign = [];
        if ($expression[0] !== '-') $sign[] = '+';
        for ($i = 0; $i < strlen($expression); $i++) {
            if ($expression[$i] == '+' || $expression[$i] == '-') {
                $sign[] = $expression[$i];
            }
        }

        $fractions = preg_split('/(?=[+-])/', $expression);
        $prev_num = 0;
        $prev_den = 1;
        $i = 0;

        foreach ($fractions as $sub) {
            if ($sub == "") continue;
            list($num, $den) = sscanf($sub, '%d/%d');
            $g = abs($this->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($this->gcd($prev_den, $prev_num));
            $prev_num /= $g;
            $prev_den /= $g;
        }

        return "$prev_num/$prev_den";
    }

    private function gcd($a, $b) {
        while ($b != 0) {
            $t = $b;
            $b = $a % $b;
            $a = $t;
        }
        return $a;
    }
}

Ставь 👍 и забирай 📚 Базу знаний