12 反转每对括号间的子串(1190)

作者: Turbo时间限制: 1S章节: DS:栈

晚于: 2020-07-15 12:00:00后提交分数乘系数50%

截止日期: 2020-07-22 12:00:00

问题描述 :

给出一个字符串 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 中只有小写英文字母和括号

我们确保所有括号都是成对出现的

输入说明 :

输入仅含有小写英文字母和括号的字符串

输出说明 :

输出一行，表示结果

输入范例 :

(u(love)i)

输出范例：

iloveu

#include <iostream>
#include <string>
#include <stack>

#include <algorithm>
using namespace std;

class Solution {
public:
    string reverseParentheses(string s)
    {
        string res;
        stack<string> temp;
        for(int i=0;i<s.length();i++)
        {
            if(s[i]=='(')
            {
                temp.push(res);
                res="";
            }
            else if(s[i]==')')
            {
                reverse(res.begin(),res.end());
                res=temp.top()+res;
                temp.pop();
            }
            else
                res+=s[i];

        }
    return res;
    }
};

int main()
{
    string a,res="";
    cin>>a;
    res=Solution().reverseParentheses(a);
    cout<<res<<endl;
    return 0;
}
//思路：设置一个栈，如果字符是'(',把字符串入栈，再清空，为了存储下一个字符
// 如果遇到右括号，则反转字符串，把栈顶元素加上反转后的即是一次括号被开出来的过程 

/*https://leetcode-cn.com/problems/reverse-substrings-between-each-pair-of-parentheses/
solution/1190-fan-zhuan-mei-dui-gua-hao-jian-de-zi-chuan-ji/*/