1190. 反转每对括号间的子串(栈|splay)[通俗易懂]

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

给出一个字符串 s（仅含有小写英文字母和括号）。

请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。

注意，您的结果中 不应 包含任何括号。

示例 1：

输入：s = "(abcd)"
输出："dcba"
示例 2：

输入：s = "(u(love)i)"
输出："iloveu"
示例 3：

输入：s = "(ed(et(oc))el)"
输出："leetcode"
示例 4：

输入：s = "a(bcdefghijkl(mno)p)q"
输出："apmnolkjihgfedcbq"
 

提示：

0 <= s.length <= 2000
s 中只有小写英文字母和括号
我们确保所有括号都是成对出现的

1. 栈

class Solution { 
   
public:
    stack<char>s1;
    queue<char>s2;
    bool isalpha(char a){ 
   
        return a >= 'a' && a <= 'z';
    }
    string reverseParentheses(string s) { 
   
        for(auto &a : s){ 
   
            if(isalpha(a) || a == '('){ 
   
                s1.push(a);
            }
            else{ 
   
                while(s1.top() != '('){ 
   
                    s2.push(s1.top());
                    s1.pop();
                }
                s1.pop();
                while(s2.size()){ 
   
                    s1.push(s2.front());
                    s2.pop();
                }
            }
        }
        string t = "";
        while(s1.size()){ 
   
            t.append(1,s1.top());
            s1.pop();
        }
        reverse(t.begin(),t.end());
        return t;
    }
};

2. splay

#define lson tr[u].s[0]
#define rson tr[u].s[1]
const int N = 2010;
class Solution { 

public:
struct node{ 

int p,v;
int s[2];
int size,flag;
void init(int _v,int _p){ 

v = _v,p = _p;
flag = 0,size = 1;
}
}tr[N] = { 
0};
int root = 0,ctx = 0;
void pushdown(int u){ 

if(tr[u].flag){ 

swap(tr[lson].s[0],tr[lson].s[1]);
swap(tr[rson].s[0],tr[rson].s[1]);
tr[lson].flag ^= 1;
tr[rson].flag ^= 1;
tr[u].flag = 0;
}
}
void pushup(int u){ 

tr[u].size = tr[lson].size + tr[rson].size + 1;
}
void rotate(int x){ 

int y = tr[x].p,z = tr[y].p;
int k = tr[y].s[1] == x;//k是1 则x是y的右儿子，k是0，则x是y的左儿子
tr[z].s[tr[z].s[1] == y] = x,tr[x].p = z;
tr[y].s[k] = tr[x].s[k ^ 1],tr[tr[x].s[k ^ 1]].p = y;
tr[x].s[k ^ 1] = y,tr[y].p = x;
pushup(y);pushup(x);
}
void splay(int x,int k){ 
        //将x节点旋转到k节点下面
while(tr[x].p != k){ 

int y = tr[x].p,z = tr[y].p;
if(z != k){ 

if((tr[z].s[1] == y) ^ (tr[y].s[1] == x))rotate(x);
else rotate(y);
}
rotate(x);
}
if(!k)root = x;
}
void insert(char a){ 

int u = root,p = 0;
while(u)pushdown(u),p = u,u = tr[u].s[1];
u = ++ ctx;
if(p)tr[p].s[1] = u;
tr[u].init(a,p);
splay(u,0);
}
int get_th(int k){ 

int u = root;
while(true){ 

pushdown(u);
if(tr[lson].size >= k)u = lson;
else if(tr[lson].size + 1 == k)return u;
else k -= tr[lson].size + 1,u = rson;
}
return u;
}
string ans = "";
void output(int u){ 

pushdown(u);
if(lson)output(lson);
if(tr[u].v != 0)ans.append(1,tr[u].v);
if(rson)output(rson);
}
void build(int L,int R,int x){ 

int u =  ++ ctx;
tr[u].init(x,R);
tr[R].s[0] = u;
pushup(R);pushup(L);
}
stack<int>ss;
string reverseParentheses(string s) { 

int end = -1;
insert(0);
insert(0);
for(int i = 0;i < s.size();i ++){ 

if(s[i] == '('){ 

ss.push(end + 1);
}
else if(s[i] == ')'){ 

int L = ss.top() - 1;
ss.pop();
int R = end + 1;
L = get_th(L + 2);R = get_th(R + 2);
splay(L,0);splay(R,L);
int ls = tr[R].s[0];
tr[ls].flag ^= 1;
swap(tr[ls].s[0],tr[ls].s[1]);
}
else{ 

char x = s[i];
int L = end,R = end + 1;
L = get_th(L + 2);R = get_th(R + 2);
splay(L,0);splay(R,L);
build(L,R,x);
end ++;
}
}
output(root);
return ans;
}
};