参考链接

1. https://leetcode-cn.com/problems/reverse-substrings-between-each-pair-of-parentheses/
2. https://leetcode-cn.com/problems/reverse-substrings-between-each-pair-of-parentheses/solution/fan-zhuan-mei-dui-gua-hao-jian-de-zi-chu-gwpv/

题目描述

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

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

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

解题思路

与括号相关的题，一般都可以用栈解决。从左向右遍历字符串，如果遇到左括号就当前字符串入栈，进入下一层括号；如果遇到右括号，就要将当前字符串反转，然后与栈顶的字符串相加构成新的字符串，走出这一层括号；否则，将字符加入当前字符串。

另一种思路是逆序地遍历括号，每次遇到括号，都找与之匹配的另一个括号，然后反向遍历，如此循环即可。只是需要预先记录每个括号配对括号的位置。

代码

栈

class Solution {
public:
    string reverseParentheses(string s) {
        stack<string> stk;
        string str;
        for (char &ch : s)
        {
            if (ch == '(')
            {
                stk.push(str);
                str = "";
            }
            else if (ch == ')')
            {
                reverse(str.begin(), str.end());
                str = stk.top() + str;
                stk.pop();
            }
            else
            {
                str.push_back(ch);
            }
        }
        return str;
    }
};

逆序遍历括号

class Solution {
public:
    string reverseParentheses(string s) {
        int n = s.length();
        vector<int> pair(n);
        stack<int> stk;
        for (int i = 0; i < n; i ++) 
        {
            if (s[i] == '(') 
            {
                stk.push(i);
            } 
            else if (s[i] == ')') 
            {
                int j = stk.top();
                stk.pop();
                pair[i] = j, pair[j] = i;
            }
        }

        string ret;
        int index = 0, step = 1;
        while (index < n) 
        {
            if (s[index] == '(' || s[index] == ')') 
            {
                index = pair[index];
                step = -step;
            } 
            else 
            {
                ret.push_back(s[index]);
            }
            index += step;
        }
        return ret;
    }
};