016: 「百夜通い」のヒント¶

難易度: ☆☆☆

ヒント1

数字の間は8か所あります。各位置に5通りの選択肢があるので、調べる組み合わせは 5**8 個です。

ヒント2

「何も入れない」を選んだ場合は、前の数字と次の数字を連結します。たとえば 1 と 2 の間に何も入れないなら、数値は 12 になります。候補式は、123 + 45 - 67 + 8 - 9 のような空白区切りの中置記法として作ると扱いやすくなります。

ヒント3

通常の演算順位を自分で処理する代わりに、候補式を逆ポーランド記法へ変換します。前々問の infix_to_rpn を使えば、* と / の優先順位を変換側に任せられます。

ヒント4

前問で作った評価器は、スタックに float を積んでいました。この問題では fractions.Fraction を積む評価器に変えると、割り算を含む式も正確に100と比較できます。