第二回 アルゴリズム実技検定 J - ⽂字列解析 解説

問題

問題文は本家サイトにあります：第二回 アルゴリズム実技検定 J - ⽂字列解析

問題概要

英小文字と '(' と ')' からなる文字列 $S$ が与えられます。以下の操作をこれ以上操作が行えなくなるまで繰り返したとき、最終的な文字列 $S$ を答えてください。

操作：'(' や ')' を含まない文字列 $T$ に対し、'(' + $T$ + ')' のような連続部分文字列が $S$ にあったとき、その部分文字列を $T+rev(T)$ に置き換える。
　ここで、 $T$ は空文字でもよい。 $rev(T)$ は、文字列 $T$ を反転させた文字列を表す。

制約

$S$ の長さは1以上1000以下。
最終的な文字列は、1000文字を超えず、'(' や ')' を含まないように、 $S$ が与えられる。

解説

リンク先の入力例3で考えてみます。

(d(abc)e)()

この中で、まず、カッコを含まず、まわりがカッコで囲まれている文字列を探すと、abc が見つかります。これを操作により置き換えると

(dabccbae)()

となります。再び探すと、dabccbae が見つかるので、再び置き換えると

dabccbaeeabccbad()

となります。最後のカッコは、空文字がカッコで囲まれていると考えます。() は操作によって空文字に変わるので

dabccbaeeabccbad

となり、これが最終的な文字列になります。

この操作をどのようにやっていくかですが、順番に左から操作をしていけばいいでしょう。英小文字や '(' の場合は何もできないですが、 ')' が現れれば操作ができます。

')' がはじめてあらわれたとき、そこからさかのぼって、'(' を見つければいいですね。このように、データを貯めておいて、後に追加したものから順番にさかのぼっていくには、スタック stack を使うと便利です。

対応するカッコが見つかったとして、今度はカッコの内側にある文字列と、その反転した文字列とをくっつける作業を考えないといけません。ただ、これも、スタックを利用すればいいですね。

先ほどの例であれば、スタックには (d(abc と入れた後、 ')' が見つかるので、スタックから値を取り出す処理を始めていきます。1つ取り出すと c が出てくるので、これを2つくっつけて cc とします。もう1つ取り出すと b が出てくるので、前と後ろにくっつけて bccb とします。もう1つ取り出すと a が出てくるので、前と後ろにくっつけて
abccba とします。次に取り出したものは '(' なので、ここれ置き換える操作はおしまいです。これを再びスタックに入れて、操作を繰り返していきます。

カッコの対応は正しくなるように与えられるので、この操作を繰り返していけば、最終的な文字列が得られます。以上のことを踏まえると、C++で書けば、次のようになります。コードの下に、コードの説明が続きます。

#include <iostream>
#include <stack>
using namespace std;

int main() {

  string S; cin >> S;
  stack<char> st;
  for (int i = 0; i < S.size(); i++) {
    if (S[i] != ')') {
      st.push(S[i]);
    } else {
      string temp = "";
      while (true) {
        char c = st.top(); st.pop();
        if (c == '(') break;
        temp = c + temp + c;
      }
      for (int j = 0; j < temp.size(); j++) {
        st.push(temp[j]);
      }
    }
  }

  string ans = "";
  while (!st.empty()) {
    char c = st.top(); st.pop();
    ans = c + ans;
  }
  cout << ans;
  return 0;
}

文字列 $S$ を左から見ていきます。 ')' 以外の場合は、スタックに追加していきます。 ')' の場合は、文字列を順番に取り出し、 temp をはさんでいく、という処理を、'(' が出てくるまで繰り返します。これで、部分文字列とその反転をつなげたものが得られます。

$S$ の最後の文字まで処理すれば、あとはスタックに入っている結果を表示しておしまいです。