ガジェット通信 GetNews

見たことのないものを見に行こう

体験を伝える―『ガジェット通信』の考え方

面白いものを探しにいこう 本物を体験し体感しよう 会いたい人に会いに行こう 見たことのないものを見に行こう そしてそれをやわらかくみんなに伝えよう [→ガジェ通についてもっと詳しく] [→ガジェット通信フロアについて]

第124回「今週のアルゴリズム:ポーランド記法から変換して不要な括弧を除去」正解者発表

「今週のアルゴリズム」とは

「今週のアルゴリズム」問題は、毎週火曜日にちょっとした問題を出題し、正解するとニックネームを掲載していくというシリーズ問題です。そして、正解した方全員に「たいへんよくできました」バッジも付与されます。

第124回は「今週のアルゴリズム:ポーランド記法から変換して不要な括弧を除去」の問題です。

問題文「第124回 今週のお題:ポーランド記法から変換して不要な括弧を除去」

第124回「今週のアルゴリズム:ポーランド記法から変換して不要な括弧を除去」正解者発表

ポーランド記法逆ポーランド記法を使うと、括弧を使わなくても演算を一意に表記できます。
例えば、通常の式(中置記法)で

のような場合、括弧を省略すると演算順序が変わってしまいますが、ポーランド記法で

(1 + 3) * (4 + 2)

のような場合、括弧を省略すると演算順序が変わってしまいますが、ポーランド記法で

* + 1 3 + 4 2

のように記述すると、括弧は不要です。

今回は数字は1種類のみ、演算子は「+」「*」の2種類だけを考えます。
これらの数字と演算子で構成され、数字が入る場所が n 箇所あるポーランド記法の式をすべて考え、それらを通常の式(中置記法)に変換した上で、不要な(演算順序に影響がない)括弧を除去します。
(「+」よりも「*」の方が、演算の優先度が高い前提です)
この作業を行ったとき、括弧のペアがいくつ残るかを求めます。

例えば、n = 3 のときは以下の8パターンがあり、必要な括弧は全部で2ペアです。
(数字は何でも構いませんが、例えば「5」を使うと以下のようになります。)

+ + 5 5 5 => 5 + 5 + 5
+ * 5 5 5 => 5 * 5 + 5
* + 5 5 5 => (5 + 5) * 5 ← ペアが1つ
* * 5 5 5 => 5 * 5 * 5
+ 5 + 5 5 => 5 + 5 + 5
+ 5 * 5 5 => 5 + 5 * 5
* 5 + 5 5 => 5 * (5 + 5) ← ペアが1つ
* 5 * 5 5 => 5 * 5 * 5

標準入力から整数 n が与えられるとき、括弧のペアの総数を求め、標準出力に出力してください。
ただし、nは15以下の正の整数とします。

【入出力サンプル】
標準入力
3

標準出力
2

正解者

おめでとうございます!正解者のみなさんです。(新着順)

shoek様
angel様
月ポコ様
R修行中様
rw0020様
haruya様
みけCAT様
todaemon様
隈野リレケム様
Sirius1293様
ciel様
Mattsun様
hiroykam様
えちごやえちぜん様
ginneko様
toku-mori様
piloswine様
distancedsilhouette様
gmk様
おじけん様
ecdsa2024_様
rotary-o様
やまさん様
scherzo2様
painfulness様
little-bird様
せど様
KAZAMAI_NaruTo様
kobapie様
Takamura様
Azicore様
facil89様
mycar様
しなう様
wand様
smz8110様
みかんず様
Ivan様
Yasu.Hara.様
14番様
L.star様
Hira0404様
ryagi様
HHeLiBeX様
tnakao様
chat様 

CodeIQ MAGAZINEの記事一覧をみる
  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。

山寺宏一&高木渉で『ポプテピピック』

GetNews girl / GetNews boy