一、题目

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

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

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

点击查看原题

二、思路

该题有很多种解法，寻求清晰的思路去解决即可。
对字符进行反转，优先想到一种数据结构，那就是stack，入栈再出栈，就进行了反转操作。假设我们对最里面括号中字符进行反转，每个字符都入队，如果需要反转就出队再入一次。整体思路如下：

1、当字符为“)”时，代表一个括号结束，进行反转操作（出队再入队），出队直到找到“(”为止，并把“(”给pop掉 2、当字符不为“)”时，入队

按照如上操作，栈中从栈底到栈顶的字符顺序，构成我们所需答案。

三、代码

class Solution {
    public String reverseParentheses(String s) {
        char[] cs = s.toCharArray();
        Stack<Character> stack = new Stack();
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < cs.length; i++) {
            char c = cs[i];
            // 判断是否该进行反转操作
            if (c == ')') {
                // t临时存放出队元素
                List<Character> t = new ArrayList();
                while (stack.peek() != '(') {
                    t.add(stack.pop());
                }
                stack.pop();    // 由于反转了一次，需要将(去掉
                // 将反转后的字符入队
                for (char tc : t) {
                    stack.push(tc);
                }
            } else {
                stack.push(c);
            }
        }
        // 从底到顶遍历栈，获取答案
        for (char c : stack) {
            ans.append(c);
        }
        return ans.toString();
    }
}

时间复杂度为O(n)，空间复杂度为O(n)。