C++에서 각 괄호 쌍 사이의 부분 문자열 반전

소문자와 대괄호로 구성된 문자열이 있다고 가정합니다. 가장 안쪽부터 시작하여 일치하는 각 괄호 쌍의 문자열을 반대로 해야 합니다. 결과에는 대괄호가 포함되어서는 안 됩니다. 따라서 입력이 "(hel(lowo)rld)"와 같으면 출력은 "dlrlowoleh"이므로 처음부터 "(hel(lowo)rld)" → "(helowolrld)"와 같이 변경됩니다. → "드로올레".

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• n :=문자열의 크기, 길이가 n인 par라는 배열을 만들고 스택을 정의합니다. st

• 0 ~ n – 1 범위의 i에 대해

  • s[i]가 괄호를 여는 경우 st

    에 i를 삽입합니다.

  • 그렇지 않으면 s[i]가 괄호를 닫을 때 j :=st.pop(), par[i] :=j 및 par[j] :=i

• 하나의 빈 문자열 정의 ret

• for i :=0, d :=1, i 증가

  • s[i]가 여는 괄호이거나 s[i]가 닫는 괄호이면 i :=par[i], d :=-d 그렇지 않으면 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