Đảo ngược chuỗi con giữa mỗi cặp dấu ngoặc đơn trong C ++

Giả sử chúng ta có một chuỗi s bao gồm các chữ cái thường và dấu ngoặc. Chúng ta phải đảo ngược các chuỗi trong mỗi cặp dấu ngoặc đơn phù hợp, bắt đầu từ chuỗi trong cùng. Và kết quả không được chứa bất kỳ dấu ngoặc nào. Vì vậy, nếu đầu vào là "(hel (lowo) rld)", thì đầu ra sẽ là "dlrlowoleh", vì vậy ngay từ đầu, nó được thay đổi như:"(hel (lowo) rld)" → "(helowolrld)" → “dlrowoleh”.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của chuỗi, tạo một mảng được gọi là par có độ dài là n, xác định một ngăn xếp

• cho tôi trong phạm vi từ 0 đến n - 1

  • nếu s [i] đang mở ngoặc, thì hãy chèn i vào st

  • ngược lại khi s [i] đóng ngoặc đơn thì j:=st.pop (), par [i]:=j và par [j]:=i

• Xác định một chuỗi trống ret

• cho i:=0, d:=1, i

  • nếu s [i] đang mở ngoặc hoặc s [i] đang đóng ngoặc, thì i:=par [i], d:=-d nếu không thì tăng ret lên s [i]

• trả lại ret

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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)"));
}

Đầu vào

"(hel(lowo)rld)"

Đầu ra

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