1. Идея

Нужно вычислить значение выражения из дробей, где между ними стоят операции + и -, а затем вывести результат в несократимом виде.

Самый прямой способ — идти слева направо и поддерживать текущую дробь num/den.

Если к дроби num/den нужно прибавить или вычесть дробь p/q, то:

• при сложении получаем (num * q + p * den) / (den * q)
• при вычитании получаем (num * q - p * den) / (den * q)

После каждого такого шага полезно сразу сокращать дробь через gcd, чтобы числа не росли слишком быстро.

2. Наблюдения

1. Выражение вычисляется последовательно слева направо, потому что в нём только + и -, а приоритет у них одинаковый.

2. Каждая дробь задана в виде p/q, где q > 0, но после промежуточных преобразований полезно всё равно следить, чтобы знаменатель оставался положительным.

3. Если после очередной операции получилась дробь num/den, то её нужно сократить:

   • найти g = gcd(|num|, den)
   • заменить num = num / g, den = den / g

4. Если итоговый числитель равен нулю, нужно вывести строго 0/1.

5. Во входной строке между всеми токенами ровно один пробел, поэтому удобно разбить строку по пробелам:

   • на чётных позициях будут дроби,
   • на нечётных — знаки операций.

Пример: 1/2 + 1/3 - 5/6

после split() получится: ["1/2", "+", "1/3", "-", "5/6"]

3. Алгоритм

1. Считать n.
2. Считать всю строку с выражением.
3. Разбить её на токены по пробелам.
4. Прочитать первую дробь и сделать её текущим ответом: num/den.
5. Сразу сократить первую дробь.
6. Дальше идти по токенам с шагом 2:
   • взять операцию op
   • взять следующую дробь p/q
   • если op == '+', то:
     • num = num * q + p * den
     • den = den * q
   • иначе:
     • num = num * q - p * den
     • den = den * q
   • сократить дробь через gcd
   • если нужно, перенести знак в числитель
7. После обработки всех дробей:
   • если num == 0, вывести 0/1
   • иначе ещё раз сократить и вывести num/den

4. Почему это работает

Докажем, что алгоритм действительно вычисляет значение выражения правильно.

Пусть после обработки нескольких первых дробей текущий результат равен num/den.

Теперь нужно применить очередную операцию с дробью p/q.

Случай сложения

Имеем:

• текущая дробь num/den
• новая дробь p/q

Чтобы сложить их, приводим к общему знаменателю den * q:

• num/den = (num * q) / (den * q)
• p/q = (p * den) / (q * den)

Тогда сумма равна: (num * q + p * den) / (den * q)

Именно это и делает алгоритм.

Случай вычитания

Аналогично: num/den - p/q = (num * q - p * den) / (den * q)

И это тоже ровно соответствует действиям алгоритма.

Почему можно сокращать после каждого шага

Если числитель и знаменатель дроби разделить на их общий делитель, значение дроби не изменится. Значит, сокращение не влияет на правильность ответа, а только делает числа меньше.

Почему итог будет в правильном формате

• После сокращения gcd(|num|, den) = 1, значит дробь несократима.
• Если знаменатель вдруг отрицательный, мы меняем знаки у числителя и знаменателя одновременно, поэтому значение дроби не меняется, а знаменатель становится положительным.
• Если num == 0, по условию надо вывести 0/1, что алгоритм и делает.

Следовательно, алгоритм всегда выдаёт правильное значение выражения в требуемом формате.

5. Сложность

Пусть в выражении n дробей.

• Разбор строки на токены занимает O(n) по количеству токенов.
• Каждая операция обрабатывается за O(1), не считая времени на gcd.
• Всего операций n - 1.

Итоговая асимптотика:

• время: O(n * log M), где M — величина чисел, участвующих в gcd
• память: O(n) из-за хранения токенов строки

6. Код на C++17

#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <cstdlib>

using namespace std;

using i128 = __int128_t;

i128 abs128(i128 x) {
    return x >= 0 ? x : -x;
}

i128 gcd128(i128 a, i128 b) {
    a = abs128(a);
    b = abs128(b);
    while (b != 0) {
        i128 t = a % b;
        a = b;
        b = t;
    }
    return a;
}

pair<i128, i128> parse_fraction(const string& s) {
    size_t pos = s.find('/');
    long long p = stoll(s.substr(0, pos));
    long long q = stoll(s.substr(pos + 1));
    return { (i128)p, (i128)q };
}

void print128(i128 x) {
    if (x == 0) {
        cout << '0';
        return;
    }
    if (x < 0) {
        cout << '-';
        x = -x;
    }
    string s;
    while (x > 0) {
        int digit = (int)(x % 10);
        s.push_back(char('0' + digit));
        x /= 10;
    }
    for (int i = (int)s.size() - 1; i >= 0; --i) {
        cout << s[i];
    }
}

int main() {
    int n;
    cin >> n;
    cin.ignore();

    string line;
    getline(cin, line);

    vector<string> tokens;
    string cur;
    for (char ch : line) {
        if (ch == ' ') {
            if (!cur.empty()) {
                tokens.push_back(cur);
                cur.clear();
            }
        } else {
            cur.push_back(ch);
        }
    }
    if (!cur.empty()) {
        tokens.push_back(cur);
    }

    auto first = parse_fraction(tokens[0]);
    i128 num = first.first;
    i128 den = first.second;

    i128 g = gcd128(num, den);
    num /= g;
    den /= g;
    if (den < 0) {
        den = -den;
        num = -num;
    }

    for (int i = 1; i < (int)tokens.size(); i += 2) {
        char op = tokens[i][0];
        auto frac = parse_fraction(tokens[i + 1]);
        i128 p = frac.first;
        i128 q = frac.second;

        if (op == '+') {
            num = num * q + p * den;
        } else {
            num = num * q - p * den;
        }
        den = den * q;

        g = gcd128(num, den);
        num /= g;
        den /= g;

        if (den < 0) {
            den = -den;
            num = -num;
        }
    }

    if (num == 0) {
        cout << "0/1\n";
    } else {
        g = gcd128(num, den);
        num /= g;
        den /= g;
        if (den < 0) {
            den = -den;
            num = -num;
        }
        print128(num);
        cout << '/';
        print128(den);
        cout << '\n';
    }

    return 0;
}

7. Код на Python 3

from math import gcd

n = int(input())
line = input().strip()
tokens = line.split()

def parse_fraction(s):
    p, q = s.split('/')
    return int(p), int(q)

num, den = parse_fraction(tokens[0])
g = gcd(abs(num), den)
num //= g
den //= g

i = 1
while i < len(tokens):
    op = tokens[i]
    p, q = parse_fraction(tokens[i + 1])

    if op == '+':
        num = num * q + p * den
    else:
        num = num * q - p * den
    den = den * q

    g = gcd(abs(num), den)
    num //= g
    den //= g
    i += 2

if num == 0:
    print("0/1")
else:
    g = gcd(abs(num), den)
    num //= g
    den //= g
    if den < 0:
        den = -den
        num = -num
    print(f"{num}/{den}")