22430번 - Broken Cipher Generator 다국어

문제

JAG (Japanese Alumni Group) は多くのプログラマで構成される謎の組織であり,この組織の本部がある建物に入るためには毎回ある機械によって生成される暗号文を解かなくてはならない. この暗号文は,'+','-','[',']' の記号と大文字のアルファベットからなっており,以下の BNF で定義される <Cipher> によって表される.

<Cipher> ::= <String> | <Cipher><String>
<String> ::= <Letter> | '['<Cipher>']'
<Letter> ::= '+'<Letter> | '-'<Letter> |
 'A' | 'B' | 'C' | 'D' | 'E' | 'F' | 'G' | 'H' | 'I' | 'J' | 'K' | 'L' | 'M' |
 'N' | 'O' | 'P' | 'Q' | 'R' | 'S' | 'T' | 'U' | 'V' | 'W' | 'X' | 'Y' | 'Z'

ここでそれぞれの記号は以下のような意味を表す.

• +(文字) : その文字の次のアルファベットを表す (ただし 'Z' の次のアルファベットは 'A' であるとする)
• -(文字) : その文字の前のアルファベットを表す (ただし 'A' の前のアルファベットは 'Z' であるとする)
• [(文字列)] : その文字列を左右反転した文字列を表す

しかしこの暗号文を生成する機械には現在故障が発生しており,暗号文のうちアルファベットの箇所が数文字壊れて読めなくなっている場合がある.読めない文字は仮に '?' と表されている. 調査の結果,壊れた文字の埋め方は,復号後の文字列が,復号後の文字列としてありえる文字列の中で辞書順最小になるようなものであることがわかった. あなたの仕事はこの暗号文を正しく復号することである.

입력

入力は複数のデータセットから構成される. 各データセットは,上記の BNF で定義された暗号文において,一部の大文字のアルファベットが ‘?’ に置き換えられた文字列を含む 1 行からなる. 各文字列の長さは 80ドル$ 以下であると仮定してよい. また各データセットに含まれる '?' の数は 0ドル$ 以上 3ドル$ 以下であると仮定してよい.

入力の終了は '.' の1文字だけを含む行で表される.

출력

各データセットに対して,復号後の文字列が辞書順最小になるように暗号文を復号したときの,復号後の文字列を出力せよ.

제한

힌트