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

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;
    }
};