Binomial Expansion (3 kyu)

https://www.codewars.com/kata/540d0fdd3b6532e5c3000b5b

이번 문제는 3kyu치고는 쉬운 문제입니다.
string으로 정의된 함수를 풀어쓰는 문제입니다.
아래의 예시와 같은 방식으로요.

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"

그 동안 풀어온 문제와 달리, C#문제입니다.

문제의 특징을 보면, 변수명이 x, p, f식으로 변할수는 있지만, 하나만 존재합니다. 그리고 기본 함수 string을 지수 연산을 수행하는 것이 규칙입니다.

일단 이 문제를 풀기위해서 주어진 string으로부터 기본 함수 부분과 지수를 분리하는 작업을 했습니다. 간단하게 ^로 split을 했습니다.

string[] fields = expr.Split('^');
string itemStr = fields[0];
int p = int.Parse(fields[1]);

여기서 함수 string인 itemStr을 각 항으로 분리하는 작업을 했습니다.
개별 항을 정의하기 위해 아래와 같은 클래스를 만들었습니다.

variable은 기본 변수를 정의하기 위한 용도이며,
order는 각 항의 order입니다.($x$는 1, $x^2$는 2입니다)
coeff는 각 항의 coefficient입니다
이 문제에서 중요한 부분은 coefficienct가 1또는 -1일때 처리하는 방식이 되겠네요. 이때는 1이 삭제되어야 합니다.

public class itemT
{
    public string variable { get; set; }
    public int order { get; set; }
    public long coeff { get; set; }
}

개별항을 정의할 클래스를 만들었기 때문에
그 다음은 기본 함수로부터 각 항 객체를 생성했습니다.
x-1인 경우는 x와 -1인 경우 2개의 항이 만들어집니다.
이 문제에서는 시작은 무조건 2개 또는 한개 항입니다.
여기서도 1또는 -1인 경우에 대한 처리가 좀 필요했습니다.

private static List<itemT> convert(string str)
    {
        List<itemT> ret = new List<itemT>();

        str = str.Substring(1, str.Length - 2);

        string sub = null;
        for (int i = 0; i < str.Length; ++i)
        {
            if (str[i] == '+' || str[i] == '-')
                sub += str[i];
            else
            {
                int n = 0;
                if (int.TryParse(str[i].ToString(), out n))
                    sub += str[i];
                else
                {
                    itemT it = new itemT { variable = str[i].ToString(), order = 1 };

                    if (sub == null)
                        it.coeff = 1;
                    else if (sub == "-")
                        it.coeff = -1;
                    else
                        it.coeff = int.Parse(sub);

                    if (it.coeff != 0)
                        ret.Add(it);

                    sub = null;
                }
            }
        }

        if (sub != null)
        {
            itemT it = new itemT { coeff = int.Parse(sub), variable = null, order = 0 };
            if (it.coeff != 0)
                ret.Add(it);
        }

        return ret;
    }

항의 List가 만들어지면,
각 List를 곱해서 새로운 List를 생성해야 됩니다.

그 메소드는 아래와 같습니다.
각 항의 객체가 곱혀져야 하는데 order는 더해지고, coefficient는 곱하면 됩니다. 좀 더 다듬으면, itemT클래스에 * operator를 추가해도 되겠네요.

static List<itemT> calc(List<itemT> lhs, List<itemT> rhs)
    {
        Dictionary<int, List<itemT>> dic = new Dictionary<int, List<itemT>>();

        for (int i = 0; i < lhs.Count; ++i)
        {
            for (int j = 0; j < rhs.Count; ++j)
            {
                itemT i0 = lhs[i];
                itemT i1 = rhs[j];

                itemT newItem = new itemT { coeff = i0.coeff * i1.coeff, order = i0.order + i1.order };
                if (i0.variable != null)
                    newItem.variable = i0.variable;
                else if (i1.variable != null)
                    newItem.variable = i1.variable;

                if (dic.ContainsKey(newItem.order) == false)
                    dic.Add(newItem.order, new List<itemT>());

                dic[newItem.order].Add(newItem);
            }
        }

        List<itemT> ret = new List<itemT>();

        foreach (var item in dic)
        {
            if (item.Value.Count == 0)
                continue;

            if (item.Value.Count > 1)
            {
                for (int i = 1; i < item.Value.Count; ++i)
                {
                    item.Value[0].coeff += item.Value[i].coeff;
                }
            }

            ret.Add(item.Value[0]);
        }

        return ret;
    }

이렇게 각 항 List의 기본 연산 메소드까지 만들면,
아래와 같이 지수에 해당되는 횟수만큼 연산을 수행한 다음에 최종 항 List를 이용해서 string을 만드는 코드를 작성하면 됩니다.
string 만드는 부분에서 예외가 좀 많았었네요.

    public static string Expand(string expr)
    {
        Console.WriteLine(expr);

        string[] fields = expr.Split('^');
        string itemStr = fields[0];
        int p = int.Parse(fields[1]);

        if (p == 0)
            return "1";

        var aas = convert(itemStr);

        List<itemT> start = aas;
        for (int i = 1; i < p; ++i)
        {
            start = calc(start, aas);
        }

        string ret = null;
        foreach (var item in start)
        {
            if (item.variable != null)
            {
                if (item.order == 1)
                    ret += string.Format("{0}{1}{2}", item.coeff > 0 ? "+" : "", item.coeff == 1 ? "" : item.coeff == -1 ? "-" : item.coeff.ToString(), item.variable);
                else
                    ret += string.Format("{0}{1}{2}^{3}", item.coeff > 0 ? "+" : "", item.coeff == 1 ? "" : item.coeff == -1 ? "-" : item.coeff.ToString(), item.variable, item.order);
            }
            else
                ret += string.Format("{0}{1}", item.coeff > 0 ? "+" : "", item.coeff);
        }

        if (ret[0] == '+')
            ret = ret.Substring(1, ret.Length - 1);

        return ret;
    }

best 답안을 보면 Regex를 이용한 파싱이 많네요.
정규식을 다루는 것은 좀 어색해서 전 그냥 파싱하는데 앞으로는 한번 사용해 봐야겠습니다.

전체 소스

https://github.com/YongheeLee/codewars_solution/blob/main/3kyu_Binomial_Expansion.cs