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