Binomial Expansion

kata programming

مساله:

هدف از این کاتا نوشتن برنامه ای است که کارهای ریاضی انجام دهد. تابعی بنویسید به نام expand که یک عبارت تک متغیری دریافت کند و آن را گسترش دهد. فرم عبارت به صورت زیر است:

(ax+b)^n

که مقادیر a , b عدد صحیحی هستند که می تواند مثبت یا منفی باشند. مقدار x متغیر ما می باشد و n هم یک عدد است.

اگر a=1 باشد هیچ مقداری نباید جلوی متغیر قرار بگیرد.

اگر a=-1 باشد باید عبارت ‘-‘ در جلوی متغیر قرار بگیرد.

حالت گسترش یافته باید به صورت زیر باشد:

ax^b+cx^d+ex^f…

که مقادیر a, c , e ضرایب عبارت هستند، x تنها متغیر ما هست و متغیرهای b,d ,f هم توان های متغیر x می باشند.

اگر ضریب صفر باشد نباید آن تکه عبارت نمایش داده شود.


Description:

The purpose of this kata is to write a program that can do some algebra. Write a function expand that takes in an expression with a single, one character variable, and expands it. The expression is in the form (ax+b)^n where a and b are integers which may be positive or negative, x is any single character variable, and n is a natural number. If a = 1, no coefficient will be placed in front of the variable. If a = -1, a “-” will be placed in front of the variable.

The expanded form should be returned as a string in the form ax^b+cx^d+ex^f... where ac, and e are the coefficients of the term, x is the original one character variable that was passed in the original expression and bd, and f, are the powers that x is being raised to in each term and are in decreasing order. If the coefficient of a term is zero, the term should not be included. If the coefficient of a term is one, the coefficient should not be included. If the coefficient of a term is -1, only the “-” should be included. If the power of the term is 0, only the coefficient should be included. If the power of the term is 1, the caret and power should be excluded.


Examples:

KataSolution.expand("(x+1)^2");      // returns "x^2+2x+1"
KataSolution.expand("(p-1)^3");      // returns "p^3-3p^2+3p-1"
KataSolution.expand("(2f+4)^6");     // returns "64f^6+768f^5+3840f^4+10240f^3+15360f^2+12288f+4096"
KataSolution.expand("(-2a-4)^0");    // returns "1"
KataSolution.expand("(-12t+43)^2");  // returns "144t^2-1032t+1849"
KataSolution.expand("(r+0)^203");    // returns "r^203"
KataSolution.expand("(-x-1)^2");     // returns "x^2+2x+1"

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class KataSolution {
  public static String expand(String expr) {
    Pattern pattern = Pattern.compile("\\((-?\\d*)(.)([-+]\\d+)\\)\\^(\\d+)");
    Matcher matcher = pattern.matcher(expr);
    matcher.find();

    final String _a = matcher.group(1);
    final int a = _a.isEmpty() ? 1 : _a.equals("-") ? -1 : Integer.parseInt(_a);
    final String x = matcher.group(2);
    final int b = Integer.parseInt(matcher.group(3).replace("+", ""));
    final int n = Integer.parseInt(matcher.group(4).replace("+", ""));
    double f = Math.pow((double) a, n);

    if (n == 0)
      return "1";
    if (a == 0)
      return String.format("%d", (int) Math.pow((double) b, n));
    if (b == 0)
      return String.format("%d%s%s", (int) f, x, (n > 1) ? String.format("^%d", n) : "");

    final StringBuilder result = new StringBuilder();
    for (int i = 0; i <= n; i++) {
      if (f > 0 && i > 0)
        result.append("+");
      if (f < 0)
        result.append("-");
      if (i > 0 || f * f > 1)
        result.append((long) Math.abs(f));
      if (i < n)
        result.append(x);
      if (i < n - 1)
        result.append(String.format("^%d", n - i));
      f = f * (n - i) * b / (double) a / (double) (i + 1);
    }

    return result.toString();
  }
}
import java.util.Arrays;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.stream.Collectors;

public class KataSolution {

  public static int nOverK(int n, int k) {
    if (n < k)
      return 0;
    if (k == 0 || k == n)
      return 1;
    return nOverK(n - 1, k - 1) + nOverK(n - 1, k);
  }

  public static String expand(String expr) {

    Matcher m = Pattern.compile("(\\-?\\d*)([a-z])([+-])(\\-?\\d+)\\D+(\\d+)").matcher(expr);
    m.find();
    int p = Integer.parseInt(m.group(5));
    String[] str = new String[p + 1];
    int a = m.group(1).length() == 0 ? 1 : m.group(1).equals("-") ? -1 : Integer.parseInt(m.group(1));
    int b = (m.group(3).equals("-") ? -1 : 1) * Integer.parseInt(m.group(4));
    for (int i = 0; i <= p; i++) {
      long f = (long) (nOverK(p, i) * Math.pow(a, p - i) * (i == 0 ? 1 : Math.pow(b, i)));
      if (f != 0) {
        str[i] = p - i == 0 ? f + ""
            : (f == 1 ? "" : f == -1 ? "-" : f) + m.group(2) + (p - i != 1 ? "^" + (p - i) : "");
      }
    }
    return Arrays.stream(str).filter(s -> s != null).collect(Collectors.joining("+")).replaceAll("\\+\\-", "\\-");
  }
}
import java.util.regex.*;
import java.util.*;
import java.lang.*;

public class KataSolution 
{
    public static String expand(String expr) 
    {
        Pattern pattern = Pattern.compile("\\((-?\\d*)(.)([-+]\\d+)\\)\\^(\\d+)");
        Matcher matcher = pattern.matcher(expr);
        matcher.find();
      
        final String _a = matcher.group(1);
        final int a = _a.isEmpty() ? 1 : _a.equals("-") ? -1 : Integer.parseInt(_a);
        final String x = matcher.group(2);
        final int b = Integer.parseInt(matcher.group(3).replace("+", ""));
        final int n = Integer.parseInt(matcher.group(4).replace("+", ""));
        double f = Math.pow((double)a, n);
      
        if (n == 0) return "1";
        if (a == 0) return String.format("%d", (int)Math.pow((double)b, n));
        if (b == 0) return String.format("%d%s%s", (int)f, x, (n > 1) ? String.format("^%d", n) : "");
      
        final StringBuilder result = new StringBuilder();
        for (int i = 0; i <= n; i++) 
        {
            if (f > 0 && i > 0) result.append("+");
            if (f < 0) result.append("-");
            if (i > 0 || f * f > 1) result.append((long)Math.abs(f));
            if (i < n) result.append(x);
            if (i < n - 1) result.append(String.format("^%d", n - i));
            f = f * (n - i) * b / (double)a / (double)(i + 1);
        }
      
        return result.toString();
    }
}
import java.util.Objects;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class KataSolution {
    private static final Pattern PATTERN = Pattern.compile("^([+\\-])?(\\d*)([a-z])([+\\-])(\\d*)$");

    private static int binomi(final int n, final int k) {
        if ((n == k) || (k == 0)) {
            return 1;
        } else {
            return binomi(n - 1, k) + binomi(n - 1, k - 1);
        }
    }

    public static String expand(final String expr) {
        //special case: It is always 1
        if (expr.lastIndexOf("^0") > -1) {
            return "1";
        }

        final String[] expSplit = expr.split("\\^");
        final int exp = Integer.parseInt(expSplit[expSplit.length - 1]);
        final String term = expSplit[0].replace("(", "").replace(")", "");

        final Matcher matcher = PATTERN.matcher(term);
        if (!matcher.find()) {
            return "";
        }

        final String prefix = matcher.group(1);
        final String operator = matcher.group(4);
        final String coefficient1 = matcher.group(2);
        final String variable = matcher.group(3);
        final String coefficient2 = matcher.group(5);

        int parsedCoefficient1 = (Objects.isNull(coefficient1) || coefficient1.isEmpty() ? 1 : Integer.parseInt(coefficient1));
        if ("-".equals(prefix)) {
           parsedCoefficient1 = -1 * parsedCoefficient1;
        }

        int parsedCoefficient2 = Integer.parseInt(coefficient2);
        if ("-".equals(operator)) {
             parsedCoefficient2 = -1 * parsedCoefficient2;
        }

        final StringBuilder sb = new StringBuilder();
        for (int i = exp; i >= 0; i--) {
            final int bino = binomi(exp, exp - i);
            final long value = (long) (Math.pow(parsedCoefficient1, i) * Math.pow(parsedCoefficient2, exp-i)) * bino;

            if (0 == value) {
                continue;
            }

            if (value >= 0 && i != exp) {
                sb.append("+");
            } else if (value == -1 && i == exp) {
                sb.append("-");
            }

            if (i > 0 && Math.abs(value) != 1 || i == 0 && Math.abs(value) > 0) {
                sb.append(value);
            }

            if (i > 1) {
                sb.append(variable).append("^").append(i);
            } else if (i > 0) {
                sb.append(variable);
            }
        }

        return sb.toString();
    }
}
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class KataSolution {
    private static final Pattern EXP_PAT = Pattern.compile("\\((.*)(\\pL)([+-]\\d+)\\)\\^(\\d+)");

    public static String expand(String expr) {
        Matcher m = EXP_PAT.matcher(expr);
        if (m.matches()) {
            long a;
            switch (m.group(1)) {
                case "":
                    a = 1L;
                    break;
                case "-":
                    a = -1L;
                    break;
                default:
                    a = Long.parseLong(m.group(1));
            }
            char x = m.group(2).charAt(0);
            long b = Long.parseLong(m.group(3));
            int n = Integer.parseInt(m.group(4));
            long[] k = new long[n + 1];
            k[0] = 1;
            for (int i = 1; i <= n; i++) {
                long c = 0;
                for (int j = 0; j <= i; j++) {
                    long t = k[j];
                    k[j] = a * c + b * t;
                    c = t;
                }
            }
            StringBuilder sb = new StringBuilder();
            for (int i = n; i >= 0; i--) {
                long t = k[i];
                if (t != 0) {
                    if (t > 0 && i < n)
                        sb.append('+');
                    if (Math.abs(t) != 1L || i == 0)
                        sb.append(t);
                    else if (t < 0)
                        sb.append('-');
                    if (i > 0) {
                        sb.append(x);
                        if (i > 1)
                            sb.append('^').append(i);
                    }
                }
            }
            return sb.toString();
        } else
            throw new IllegalArgumentException("Illegal expression: " + expr);
    }
}

دیدگاهتان را بنویسید