AOJ 0041 （Expression : 式）

【問題】

https://onlinejudge.u-aizu.ac.jp/problems/0041

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0041

【解説】

整数a,b,c,dと演算子+,-,*および()を使用して、10を作ることのできる式を求める問題。肝は全てのパターンをもれなく重複なく数え上げることができるかどうかとなる。

まず、()による優先順位付けは取り漏らす可能性があるため、逆ポーランド記法にて考えることとした。数を4つ（〇）、演算子を3つ（×）使用する場合の逆ポーランド記法として考えられるパータンは、

1. 〇〇×〇〇××
2. 〇〇×〇×〇×
3. 〇〇〇×〇××
4. 〇〇〇××〇×
5. 〇〇〇〇×××

の5パータンのみである。なぜなら、演算子が出現する場合には、スタックに数値が2つ以上格納されている必要があるため、必ず使用した演算子の数より多く数値が格納されている必要がある。そのため、初めの2つは「〇〇」から始まる必要がある。また、処理の最後は演算となるため、末尾は「×」となる必要がある。よって3文字目～6文字目に〇2個、×2個を入れる組み合わせの6パターンのうち「××○○」となるものを除く5パターンが候補となる。（「××○○」だと「〇〇××〇〇×」となり、2つ目の演算子が出現した時点で演算子超過となる。）

あとは、各〇に数値のa,b,c,dの順列を、各×に演算子+,-.*をそれぞれ入れて、逆ポーランド記法の演算を行い、10になるかを全探索していく。順列の求め方については、集合から任意の1要素を取り出し、取り出した要素を除いた集合からさらに任意の1要素を取り出し、取り出した要素を除いた・・・・という処理を再帰的に行っていくことで求めることができる。

ここで、上記の2～5のパターンに着目すると、これらは全て「任意の2数を演算する」⇒「その結果に残りの数のいずれかを演算する」⇒「その結果に残りの数を演算する」という処理となるため、このうち1パーンのみを処理すれば十分である。よって、上記の1と2のパターンについてのみ探索し、判定結果によって0または逆ポーランド記法を中置記法に直した文字列を出力すればよい。

【コード】