問題概要

以下の BNF によって定義された文字列が与えられる。

<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' であるとする)
"[(文字列)]" : その文字列を左右反転した文字列を表す

与えられた文字列を復元せよ。ただし '?' は 'A'〜'Z' のいずれかを意味する。復元した文字列が辞書順最小となるようにせよ。たとえば、次のようになる。

A+A++A　→　ABC
Z-Z--Z+-Z　→　ZYXZ
[ESREVER]　→　REVERSE
J---?---J　→　JAG
++++++++A+++Z-----------A+++Z　→　ICPC
[[++-+--?[--++-?++-+++L]][-+-----+-O]]++++---+L　→　JAPAN

制約

$1 \le |S| \le 80$
$'?' の個数は 3 個以下$

考えたこと

カッコ列に関する問題なので stack で扱えそうと考えた

st：「左カッコ」「+ と - の個数換算値」を積むスタック
res：答えを表す文字列、ただしどの場所を反転すべきかを明らかにしながら構文解析を進めるために、途中結果では左カッコ '[' も含めて管理することにした。

下のコードでは、反転を愚直にシミュレーションしているため、計算量は $O(|S|^{2})$ となる。

#include <bits/stdc++.h>
using namespace std;

string solve(const string &S) {
    string res = "";
    vector<int> st;
    const int kakko = 1000;
    for (auto c : S) {
        if (c == '[') st.push_back(kakko), res += "[";
        else if (c == ']') {
            string tmp = "";
            while (!res.empty() && res.back() != '[') {
                tmp += res.back();
                res.pop_back();
            }
            if (!res.empty() && res.back() == '[') res.pop_back();
            res += tmp;
            st.pop_back();
        }
        else if (c == '+' || c == '-') {
            int add = (c == '+' ? 1 : -1);
            if (st.empty() || st.back() == kakko) st.push_back(add);
            else {
                int num = st.back();
                st.pop_back();
                st.push_back(num+add);
            }
        }
        else {
            if (st.empty() || st.back() == kakko) {
                char nc = (c != '?' ? c : 'A');
                res += nc;
            }
            else {
                int num = st.back();
                st.pop_back();
                int ord = c - 'A';
                int nord = (ord + num) % 26;
                if (nord < 0) nord += 26;
                char nc = 'A' + nord;
                res += (c != '?' ? nc : 'A');
            }
        }
    }
    return res;
}

int main() {
    string S;
    while (cin >> S) {
        if (S == ".") break;
        cout << solve(S) << endl;
    }
}