고장 난 암호문 생성기
시간 제한8초메모리 제한512 MB
더하기/빼기 이동과 대괄호 뒤집기가 섞인 암호문에서 물음표를 채워 복호화한 결과가 사전순으로 가장 작아지도록 만든다.
문제
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로 정의된 암호문에서 일부 대문자 알파벳이 '?'로 바뀐 문자열 한 줄로 이루어진다. 각 문자열의 길이는 이하라고 가정해도 좋다. 또 각 데이터셋에 포함된 '?'의 개수는 이상 이하라고 가정해도 좋다.
입력의 끝은 '.' 한 글자만 포함하는 줄로 나타낸다.
출력
각 데이터셋에 대해, 복호화한 문자열이 사전순으로 가장 작아지도록 암호문을 복호화했을 때의 복호화 결과 문자열을 출력한다.