ABC045-C たくさんの数式

■■■問題■■■

1以上9以下の数字のみからなる文字列Sが与えられます。

この文字列の中で、あなたはこれら文字と文字の間のうち、
いくつかの場所に+を入れることができます。一つも入れなくてもかまいません。
ただし、+が連続してはいけません。

このようにして出来る全ての文字列を数式とみなし、和を計算することができます。
ありうる全ての数式の値を計算し、その合計を出力してください。

■■■入力■■■

S

●1 <= |S| <= 10
●Sに含まれる文字は全て1〜9の数字

■■■出力■■■

ありうる全ての数式の値の総和を1行に出力せよ。

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("125");
            //176
            //考えられる数式としては、
            //125、1+25、12+5、1+2+5 の4通りがあります。
            //それぞれの数式を計算すると、
            //●125
            //●1+25=26
            //●12+5=17
            //●1+2+5=8
            //となり、これらの総和は 125+26+17+8=176 となります。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("9999999999");
            //12656242944
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct JyoutaiDef
    {
        internal int CurrInd;
        internal long CurrSum;
        internal long TotalSum;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        string S = InputList[0];
        int UB = S.Length - 1;

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrInd = 0;
        WillPush.CurrSum = 0;
        WillPush.TotalSum = 0;
        Stk.Push(WillPush);

        long Answer = 0;
        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();

            //クリア判定
            if (Popped.CurrInd > UB) {
                Answer += Popped.CurrSum + Popped.TotalSum;
                continue;
            }

            int CurrNum = int.Parse(S[Popped.CurrInd].ToString());

            //+を使う経路
            if (Popped.CurrInd > 0) {
                WillPush.CurrInd = Popped.CurrInd + 1;
                WillPush.CurrSum = CurrNum;
                WillPush.TotalSum = Popped.TotalSum + Popped.CurrSum;
                Stk.Push(WillPush);
            }

            //+を使わない経路
            WillPush.CurrInd = Popped.CurrInd + 1;
            WillPush.CurrSum = Popped.CurrSum * 10 + CurrNum;
            WillPush.TotalSum = Popped.TotalSum;
            Stk.Push(WillPush);
        }
        Console.WriteLine(Answer);
    }
}

解説

2の9乗しかないので、深さ優先探索でナイーブに解いてます。