Parse [第二回 アルゴリズム実技検定 J]

https://atcoder.jp/contests/past202004-open/tasks/past202004_j

前提知識

• 構文解析

解説

https://atcoder.jp/contests/past202004-open/submissions/12898808

この問題は適切に構文解析を行えるかを問う問題。
構文解析の一番単純な手法として再帰で行う方法がある。
説明がとても難しいのだが、先頭から順番に見ていって、(が出てきたら、
再帰を1回行って、(???)の???の部分の文字列を取得する。
取得した文字列がresだとしたら、それを反転させた文字列serを作って、(???)の評価結果としてres+serを返す。
普通の文字ならその文字+それ以降の文字で再帰を続けていく。
これを続けていくといい。
あと、注意すべき点として、先頭から見ていったときにindexが行き過ぎてしまうことがあるので、
番兵として末尾に#を自分はつけている。
（=の方が見た目クールだけど）

string S;
int idx = 0;
//---------------------------------------------------------------------------------------------------
string parse() {
    if (S[idx] == '(') {
        idx++;
        string res = parse();
        idx++;

        string ser = res;
        reverse(all(ser));
        return res + ser + parse();
    }
    else if ('a' <= S[idx] && S[idx] <= 'z') {
        string res = S.substr(idx, 1);
        idx++;
        res += parse();
        return res;
    }
    return "";
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S;
    S += "#";
    cout << parse() << endl;
}