異世界数式 [COLOCON -Colopl programming contest 2018- Final B]

https://beta.atcoder.jp/contests/colopl2018-final-open/tasks/colopl2018_final_b

必要知識

• 構文解析

解法

https://beta.atcoder.jp/contests/colopl2018-final-open/submissions/1996734

構文解析をする。ICPCでは頻出であるが、他の競プロ問題ではあまり見ない。
色んな流派があるような感じがあるが、下の解法を少しだけ詳しく解説しておく。
indexをiとして保持しながら構文解析を進めていく。
　
今、S[i]が数字である場合。「if ('0' <= S[i] and S[i] <= '9')」
この場合は数字としてパースして返す。
while ('0' <= S[i] and S[i] <= '9')で数字じゃない文字が来るまで数字を返していく。
もし数字でない文字が来たら、数字全てを合わせたやつを返す。
　
今、S[i]が数字でない場合。「else」
この場合は今回の構文では必ず演算が来ているので、演算の記号をcとして保存しておく。
i++をして演算の記号の次に移動する。
「while(S[i] != ')')」で)が来るまでパースを実行する。
最初は'('を指しているのでi++をしてからf()を再帰的に呼び出す。
これで演算の括弧の中の最初のindexからパースを始めてくれる。
帰ってきたら、それと演算記号を答えに追加する。
2回目のループでは','か')'となるので、','なら以上の処理を続行し、')'ならやめる。
ループを抜けたらi++をして')'の次にindexを移しておく。
返す文字列は最後が演算記号になっているので、これを')'に変えて返す。
　
このように再帰を繰り返しながら構文解析をする手法がある。
拡張として演算に優先順位があったり、色々難しいものもあるが、今回の構文解析は入門にはちょうどいいかもしれない。
番兵として一番最後に演算に関係ない文字(例えば"=")をつけておくとREを防げる。

string S;
int i = 0;
string f() {
    if ('0' <= S[i] and S[i] <= '9') {
        string res = "";
        while ('0' <= S[i] and S[i] <= '9') {
            res += S[i];
            i++;
        }
        return res;
    } else {
        char c = S[i];
        i++;
        string res = "(";
        while (S[i] != ')') {
            i++;
            res += f();
            res += c;
        }
        i++;
        res[res.length() - 1] = ')';
        return res;
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S;
    S += "=";
    cout << f() << endl;
}