C ++中每对括号之间的反向子字符串

假设我们有一个由小写字母和方括号组成的字符串s。我们必须从最里面的一对开始反转每对匹配括号中的字符串。并且结果中不应包含任何括号。因此，如果输入像“（hel(lowo)rld）”，那么输出将是“ dlrlowoleh”，因此从一开始就将其更改为：“（hel(lowo)rld）”→“(helowolrld)” →“ dlrowoleh”。

为了解决这个问题，我们将遵循以下步骤-

• n：=字符串的大小，创建一个名为par的数组，其长度为n，定义一个堆栈st

• 对于i，范围为0至n – 1

• 如果s [i]是开括号，则将i插入st

• 否则，当s [i]是右括号时，则j：= st.pop()，par [i]：= j和par [j]：= i

• 定义一个空字符串ret

• 对于i：= 0，d：= 1，i <n，将i增加d

• 如果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