AtCoder ABC 307 D - Mismatched Parentheses (3Q, 茶色, 400 点)

カッコ列に関連してシミュレーションしていく問題！

• 問題へのリンク

問題概要

英小文字と文字 '('、')' からなる長さ の文字列 が与えられる。この文字列に対して、次の操作を繰り返す。

「文字 '(' と ')' に挟まれた部分文字列であって、カッコ文字を含まない部分を削除し、それらの両端の '(' と ')' も削除する」

この操作をどのように繰り返しても、結果は一意に定まる。その結果の文字列を出力せよ。

制約

• 

考えたこと

いわゆるカッコ列の整合性判定問題の亜種！！

カッコ列整合性判定問題においては、スタックを用いて、カッコ列を左から順に見ていき、

• '(' が来たら、スタックに push する
• ')' が来たら、スタックの終端が ')' であったらその文字をスタックから pop する (新たな push はしない)

という操作を繰り返していき、最終的にスタックが空になるかどうかを確かめるという手法が存在する。

今回の問題

今回も同様の手法で解ける。同様にスタックを用いる。また、スタック内部に '(' が何個残っているかを表す変数 height も用意しておく。そして文字列 を左から順に見ていき、次のように処理すればよい。

---

• 英小文字が来たら、スタックに push する
• '(' が来たら、スタックに push して、height を 1 増やす
• ')' が来たら、
  • height が 0 のとき：スタックに push する
  • height が 1 以上のとき：スタックから ')' が取り出されるまで pop し続けて、height を 1 減らす

---

計算量は となる。

コード

ここでは、string 型変数それ自体をスタックとして活用した。

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

int main() {
    int N;
    string S;
    cin >> N >> S;
    string res;
    int height = 0;
    for (auto c : S) {
        if (c == ')' && height) {
            while (!res.empty() && res.back() != '(') res.pop_back();
            res.pop_back();
            --height;
        } else if (c == '(') {
            res += c;
            ++height;
        } else {
            res += c;
        }
    }
    cout << res << endl;
}