← Static tasks

592. Fraction Addition and Subtraction

leetcode medium

#csharp#leetcode#math#medium#string#trie

Task

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

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

Пример:

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

Output: "1/3"

C# solution

matched/original
using System;
using System.Collections.Generic;
public class Solution {
    public string FractionAddition(string expression) {
        var sign = new List<char>();
        if (expression[0] != '-') sign.Add('+');
        foreach (char ch in expression) {
            if (ch == '+' || ch == '-') sign.Add(ch);
        }
        int prevNum = 0, prevDen = 1, i = 0;
        var fractions = expression.Replace("-", "+-").Split(new char[] { '+' }, StringSplitOptions.RemoveEmptyEntries);
        
        foreach (var sub in fractions) {
            var fraction = sub.Split(new char[] { '/' });
            int num = int.Parse(fraction[0]);
            int den = int.Parse(fraction[1]);
            int g = Math.Abs(Gcd(prevDen, den));
            if (sign[i++] == '+') prevNum = prevNum * den / g + num * prevDen / g;
            else prevNum = prevNum * den / g - num * prevDen / g;
            prevDen = prevDen * den / g;
            g = Math.Abs(Gcd(prevDen, prevNum));
            prevNum /= g;
            prevDen /= g;
        }
        
        return $"{prevNum}/{prevDen}";
    }
    private int Gcd(int a, int b) {
        while (b != 0) {
            int t = b;
            b = a % b;
            a = t;
        }
        return a;
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public string FractionAddition(string expression) {
        var sign = new List<char>();
        if (expression[0] != '-') sign.push_back('+');
        foreach (char ch in expression) {
            if (ch == '+' || ch == '-') sign.push_back(ch);
        }
        int prevNum = 0, prevDen = 1, i = 0;
        var fractions = expression.Replace("-", "+-").Split(new char[] { '+' }, StringSplitOptions.RemoveEmptyEntries);
        
        foreach (var sub in fractions) {
            var fraction = sub.Split(new char[] { '/' });
            int num = int.Parse(fraction[0]);
            int den = int.Parse(fraction[1]);
            int g = abs(Gcd(prevDen, den));
            if (sign[i++] == '+') prevNum = prevNum * den / g + num * prevDen / g;
            else prevNum = prevNum * den / g - num * prevDen / g;
            prevDen = prevDen * den / g;
            g = abs(Gcd(prevDen, prevNum));
            prevNum /= g;
            prevDen /= g;
        }
        
        return $"{prevNum}/{prevDen}";
    }
    private int Gcd(int a, int b) {
        while (b != 0) {
            int t = b;
            b = a % b;
            a = t;
        }
        return a;
    }
}

Java solution

matched/original
class Solution {
  public String fractionAddition(String expression) {
    List<Character> sign = new ArrayList<>();
    if (expression.charAt(0) != '-') sign.add('+');
    for (int i = 0; i < expression.length(); i++) {
      if (expression.charAt(i) == '+' || expression.charAt(i) == '-')
        sign.add(expression.charAt(i));
    }
    int prev_num = 0, prev_den = 1, i = 0;
    for (String sub : expression.split("(\\+)|(-)")) {
      if (sub.length() > 0) {
        String[] fraction = sub.split("/");
        int num = (Integer.parseInt(fraction[0]));
        int den = (Integer.parseInt(fraction[1]));
        int g = Math.abs(gcd(den, prev_den));
        if (sign.get(i++) == '+') prev_num = prev_num * den / g + num * prev_den / g;
        else prev_num = prev_num * den / g - num * prev_den / g;
        prev_den = den * prev_den / g;
        g = Math.abs(gcd(prev_den, prev_num));
        prev_num /= g;
        prev_den /= g;
      }
    }
    return prev_num + "/" + prev_den;
  }

  public int gcd(int a, int b) {
    while (b != 0) {
      int t = b;
      b = a % b;
      a = t;
    }
    return a;
  }
}

JavaScript solution

matched/original
var fractionAddition = function(expression) {
    let sign = [];
    if (expression[0] !== '-') sign.push('+');
    for (let char of expression) {
        if (char === '+' || char === '-') sign.push(char);
    }

    let fractions = expression.replace(/-/g, '+-').split('+').filter(f => f.length > 0);
    let prevNum = 0, prevDen = 1, i = 0;

    for (let sub of fractions) {
        let [num, den] = sub.split('/').map(Number);
        let g = gcd(prevDen, den);
        if (sign[i++] === '+') prevNum = prevNum * den / g + num * prevDen / g;
        else prevNum = prevNum * den / g - num * prevDen / g;
        prevDen = prevDen * den / g;
        g = Math.abs(gcd(prevDen, prevNum));
        prevNum /= g;
        prevDen /= g;
    }

    return `${prevNum}/${prevDen}`;
};

function gcd(a, b) {
    while (b !== 0) {
        [a, b] = [b, a % b];
    }
    return a;
}

Python solution

matched/original
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}"

Go solution

matched/original
package main

import (
    "fmt"
    "strconv"
    "strings"
)

func fractionAddition(expression string) string {
    sign := []byte{}
    if expression[0] != '-' {
        sign = append(sign, '+')
    }
    for i := 0; i < len(expression); i++ {
        if expression[i] == '+' || expression[i] == '-' {
            sign = append(sign, expression[i])
        }
    }

    fractions := strings.FieldsFunc(expression, func(r rune) bool { return r == '+' || r == '-' })
    prevNum, prevDen := 0, 1
    i := 0

    for _, sub := range fractions {
        if sub == "" {
            continue
        }
        parts := strings.Split(sub, "/")
        num, _ := strconv.Atoi(parts[0])
        den, _ := strconv.Atoi(parts[1])
        g := gcd(prevDen, den)
        if sign[i] == '+' {
            prevNum = prevNum*den/g + num*prevDen/g
        } else {
            prevNum = prevNum*den/g - num*prevDen/g
        }
        prevDen = prevDen * den / g
        g = abs(gcd(prevDen, prevNum))
        prevNum /= g
        prevDen /= g
        i++
    }

    return fmt.Sprintf("%d/%d", prevNum, prevDen)
}

func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

Explanation

Algorithm

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

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

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

😎