Q42 1つの数字で作る1234

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        for (int LoopNumCnt = 1; LoopNumCnt < int.MaxValue; LoopNumCnt++) {
            var AnswerList = new List<string>();
            for (int LoopNum = 1; LoopNum <= 9; LoopNum++) {
                AnswerList.AddRange(DeriveAnswerList(LoopNum, LoopNumCnt));
            }
            if (AnswerList.Count > 0) {
                Console.WriteLine("数字の個数={0}の解を発見", LoopNumCnt);
                AnswerList.ForEach(X => Console.WriteLine("{0} = 1234", X));
                break;
            }
        }
    }

    //数字と個数と引数として、1234になる数式のListを返す
    static List<string> DeriveAnswerList(int pNum, int pNumCnt)
    {
        var WillReturn = new List<string>();

        var SuusikiList = new List<string>();
        var stk = new Stack<string>();
        var InitStr = new System.Text.StringBuilder();
        for (int I = 1; I <= pNumCnt; I++) {
            InitStr.Append(pNum);
            if (I < pNumCnt) InitStr.Append('□');
        }
        stk.Push(InitStr.ToString());

        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, "/"));
        }
        foreach (string EachStr in SuusikiList) {
            if (CalcFromRPN(ToRPN(EachStr)) == 1234) {
                WillReturn.Add(EachStr);
            }
        }
        return WillReturn;
    }

    //数式を逆ポーランド記法にした配列を返す
    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 2;
        return 0;
    }

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

        foreach (string EachStr in pRPNArr) {
            if (EachStr == "+" || EachStr == "-" || EachStr == "*" || EachStr == "/") {
                long exp2 = stk.Pop();
                long exp1 = stk.Pop();
                if (EachStr == "+") stk.Push(exp1 + exp2);
                if (EachStr == "-") stk.Push(exp1 - exp2);
                if (EachStr == "*") stk.Push(exp1 * exp2);
                if (EachStr == "/") stk.Push(exp1 / exp2);
                continue;
            }
            stk.Push(long.Parse(EachStr));
        }
        return stk.Pop();
    }
}

実行結果

数字の個数=7の解を発見
99999/9/9 = 1234

解説

数式を逆ポーランド記法に変換してから、計算してます。