COLOCON -Colopl programming contest 2018- Final B - 異世界数式 (1Q)

スタックを用いると楽に構文解析できる！

• 問題へのリンク

問題概要

+(1,+(+(2,3)),+(4,+(5)))

のような形式の入力を

(1+((2+3))+(4+(5)))

のように変換せよ (詳しくは問題文参照)。

制約

• 

考えたこと

スタックを用いて「演算子」を格納しておく。

• ',' が来たら、スタックの末尾にある演算子を活用する
• ')' が来たら、スタックの末尾にある演算子を除去する

というようにすれば OK。計算量は となる。

コード

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

int main() {
    string S, res = "", op_stk;
    cin >> S;
    for (auto c : S) {
        if (c == '+' || c == '-' || c == '*' || c == '/') {
            op_stk += c;
        } else if (c == ',') {
            res += op_stk.back();
        } else if (c == ')') {
            res += c;
            op_stk.pop_back(); 
        } else {
            res += c;
        }
    }
    cout << res << endl;
}