C++の括弧の各ペア間のサブストリングを逆にする

小文字と括弧で構成される文字列sがあるとします。一致する括弧の各ペアの文字列を、最も内側の括弧から始めて逆にする必要があります。また、結果に角かっこを含めることはできません。したがって、入力が「（hel（lowo）rld）」の場合、出力は「dlrlowoleh」になるため、最初から「（hel（lowo）rld）」→「（helowolrld）」のように変更されます。 →「dlrowoleh」。

これを解決するには、次の手順に従います-

• n：=文字列のサイズ、長さがnのparという配列を作成し、スタックst

  を定義します。

• 0からn–1の範囲のiの場合

  • s [i]が開き括弧の場合は、iをstに挿入します

  • それ以外の場合、s [i]が括弧を閉じているときは、j：=st.pop（）、par [i]：=j、およびpar [j]：=i

• 空の文字列retを1つ定義します

• for i：=0、d：=1、i

  • s [i]が開き括弧であるか、s [i]が閉じ括弧である場合、i：=par [i]、d：=-d、それ以外の場合はretをs [i]

    増やします。

• retを返す

例（C ++）

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   void out(vector <int>& v){
      for(int i = 0; i < v.size(); i++){
         cout << v[i] << " " ;
      }
      cout << endl;
   }
   string reverseParentheses(string s) {
      int n = s.size();
      vector <int> par(n);
      stack <int> st;
      for(int i = 0; i < n; i++){
         if(s[i] == '('){
            st.push(i);
         }
         else if(s[i] == ')'){
            int j = st.top();
            st.pop();
            par[i] = j;
            par[j] = i;
         }
      }
      string ret = "";
      for(int i = 0, d = 1; i < n; i += d){
         if(s[i] == '(' || s[i] == ')'){
            i = par[i];
            d = -d;
         }
         else{
            ret += s[i];
         }
      }
      out(par);
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.reverseParentheses("(hel(lowo)rld)"));
}

入力

"(hel(lowo)rld)"

出力

13 0 0 0 9 0 0 0 0 4 0 0 0 0
dlrlowoleh