C# short solution (Regex, Linq and GCD)


  • 1
    E

    Felt like having fun with LINQ.

    using System.Text.RegularExpressions;
    
    public class Solution
    {
        public string FractionAddition(string expression)
        {
            return string.Join("/", 
                Regex.Matches(expression, @"(-?\d+)\/(\d+)").OfType<Match>()
                .Select(m => new[] { int.Parse(m.Groups[1].Value), int.Parse(m.Groups[2].Value) })
                .Aggregate(new[] { 0, 1 }, (p, c) => Normalize(p[0] * c[1] + p[1] * c[0], p[1] * c[1])));
        }
    
        private int Gcd(int a, int b) => a == 0 ? Math.Abs(b) : Gcd(b % a, a);
    
        private int[] Normalize(int n, int d) => new[] { n / Gcd(n, d), d / Gcd(n, d) };
    }
    
    1. First we convert the string expression to an enumerable of fractions. Each fraction is an int[2] array. Regular expression expects fractions like "n/d" where n could be negative. Plus signs are disregarded completely, we don't need them:
    Regex.Matches(expression, @"(-?\d+)\/(\d+)").OfType<Match>()
        .Select(m => new[] { int.Parse(m.Groups[1].Value), int.Parse(m.Groups[2].Value) })
    
    1. Next we aggregate the results (this Linq function's analogue in javascript is called reduce, for example). We always start from value 0/1 and then sum it with the first number using the fraction rules from school: a/b + c/d = (a*d + b*c) / b * d. After that we use the Normalize helper function, which finds the greatest common denominator for numerator and denominator and uses it to normalize our current fraction.
    .Aggregate(new[] { 0, 1 }, (p, c) => Normalize(p[0] * c[1] + p[1] * c[0], p[1] * c[1])));
    
    1. After the last number was added, the resulting nominator and denominator are joined with "/" in between them with: string.Join

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.