8-21 小町算

問題

1□2□3□4□5□6□7□8□9 = 100
という数式の□の中に、
＋,−,×,÷,空白
のいずれかを入れて数式を完成させます。

ソース

using System;
using System.Collections.Generic;

internal class CKabunSuu
{
    private long mBunshi; //分子
    private long mBunbo; //分母

    //コンストラクタ (値指定)
    internal CKabunSuu(long pBunshi, long pBunbo)
    {
        mBunshi = pBunshi;
        mBunbo = pBunbo;
    }

    //コンストラクタ (インスタンス指定)
    internal CKabunSuu(CKabunSuu pIns)
    {
        mBunshi = pIns.mBunshi;
        mBunbo = pIns.mBunbo;
    }

    //加算用メソッド (インスタンス指定)
    internal void Add(CKabunSuu pIns)
    {
        long SavedBunbo = mBunbo; //通分する前の分母

        //通分してから、加算
        mBunbo *= pIns.mBunbo;
        mBunshi = this.mBunshi * pIns.mBunbo + pIns.mBunshi * SavedBunbo;
        Yakubun();
    }

    //減算用メソッド (インスタンス指定)
    internal void Subtract(CKabunSuu pIns)
    {
        Add(new CKabunSuu(-pIns.mBunshi, pIns.mBunbo));
    }

    //乗算用メソッド (インスタンス指定)
    internal void Prod(CKabunSuu pIns)
    {
        this.mBunshi *= pIns.mBunshi;
        this.mBunbo *= pIns.mBunbo;
        Yakubun();
    }

    //除算用メソッド (インスタンス指定)
    internal void Div(CKabunSuu pIns)
    {
        this.mBunshi *= pIns.mBunbo;
        this.mBunbo *= pIns.mBunshi;
        Yakubun();
    }

    //約分
    private void Yakubun()
    {
        if (mBunshi == 0) return;

        long GCD = DeriveGCD(mBunshi, mBunbo);
        if (GCD == 1) return;
        mBunshi /= GCD;
        mBunbo /= GCD;
    }

    //ユークリッドの互除法で2数の最大公約数を求める
    private long DeriveGCD(long pVal1, long pVal2)
    {
        pVal1 = Math.Abs(pVal1);
        pVal2 = Math.Abs(pVal2);

        long WarareruKazu = Math.Max(pVal1, pVal2);
        long WaruKazu = Math.Min(pVal1, pVal2);

        while (true) {
            long Amari = WarareruKazu % WaruKazu;
            if (Amari == 0) return WaruKazu;
            WarareruKazu = WaruKazu;
            WaruKazu = Amari;
        }
    }

    //分数の値を返す
    internal decimal DecimalValue
    {
        get { return (decimal)mBunshi / mBunbo; }
    }
}

class Program
{
    static void Main()
    {
        var SuusikiList = new List<string>();

        var Stk = new Stack<string>();
        Stk.Push("1□2□3□4□5□6□7□8□9");

        while (Stk.Count > 0) {
            string Popped = Stk.Pop();

            int Ind = Popped.IndexOf('□');
            if (Ind == -1) {
                SuusikiList.Add(Popped);
                continue;
            }

            string wkStr = Popped.Remove(Ind, 1);
            Stk.Push(wkStr);
            Stk.Push(wkStr.Insert(Ind, "+"));
            Stk.Push(wkStr.Insert(Ind, "-"));
            Stk.Push(wkStr.Insert(Ind, "*"));
            Stk.Push(wkStr.Insert(Ind, "/"));
        }

        int AnswerNo = 0;
        foreach (string AnyStr in SuusikiList) {
            if (CalcFromRPN(ToRPN(AnyStr)) == 100M)
                Console.WriteLine("Answer{0}   {1} = 100", ++AnswerNo, AnyStr);
        }
    }

    //数式を逆ポーランド記法にした配列を返す
    static string[] ToRPN(string pTargetStr)
    {
        var WillReturn = new List<string>();

        var Stk = new Stack<string>();
        string[] WkStrArr = MakeNumAndExpArr(pTargetStr);

        foreach (string EachStr in WkStrArr) {
            if (EachStr == "+" || EachStr == "-" || EachStr == "*" || EachStr == "/") {
                int Priority = DerivePriority(EachStr);

                while (Stk.Count > 0 && Priority <= DerivePriority(Stk.Peek())) {
                    WillReturn.Add(Stk.Pop());
                }
                Stk.Push(EachStr);
            }
            else WillReturn.Add(EachStr);
        }
        while (Stk.Count > 0) WillReturn.Add(Stk.Pop());
        return WillReturn.ToArray();
    }

    //数式から数値と演算子の配列を作成
    static string[] MakeNumAndExpArr(string pTargetStr)
    {
        var WillReturn = new List<string>();
        var sb = new System.Text.StringBuilder();

        foreach (Char EachChar in pTargetStr) {
            if (EachChar == '+' || EachChar == '-' || EachChar == '*' || EachChar == '/') {
                WillReturn.Add(sb.ToString()); sb.Length = 0;
                WillReturn.Add(EachChar.ToString());
            }
            else sb.Append(EachChar);
        }
        WillReturn.Add(sb.ToString());
        return WillReturn.ToArray();
    }

    //演算子のプライオリティを返す
    static int DerivePriority(string pOperator)
    {
        if (pOperator == "+") return 1;
        if (pOperator == "-") return 1;
        if (pOperator == "*") return 2;
        if (pOperator == "/") return 3;
        return 0;
    }

    //逆ポーランド記法のListジェネリックを計算した結果を返す
    static decimal CalcFromRPN(string[] pRPNArr)
    {
        var Stk = new Stack<CKabunSuu>();

        foreach (string EachStr in pRPNArr) {
            if (EachStr == "+" || EachStr == "-" || EachStr == "*" || EachStr == "/") {
                CKabunSuu exp2 = Stk.Pop(); //exp2は中身を変更しないので参照でOK
                CKabunSuu exp1 = new CKabunSuu(Stk.Pop());
                if (EachStr == "+") { exp1.Add(exp2); Stk.Push(exp1); }
                if (EachStr == "-") { exp1.Subtract(exp2); Stk.Push(exp1); }
                if (EachStr == "*") { exp1.Prod(exp2); Stk.Push(exp1); }
                if (EachStr == "/") { exp1.Div(exp2); Stk.Push(exp1); }
                continue;
            }
            Stk.Push(new CKabunSuu(long.Parse(EachStr), 1));
        }
        return Stk.Pop().DecimalValue;
    }
}

実行結果

省略
Answer96   12+34+5*6+7+8+9 = 100
Answer97   123-4-5-6-7+8-9 = 100
Answer98   123-45-67+89 = 100
Answer99   123+4*5-6*7+8-9 = 100
Answer100   123+4-5+67-89 = 100
Answer101   123+45-67+8-9 = 100

解説

数式を逆ポーランド記法に変換して、計算してます。
誤差防止のために仮分数クラスを使ってます。