You are given a string s that consists of lower case English letters and brackets.

Reverse the strings in each pair of matching parentheses, starting from the innermost one.

Your result should not contain any brackets.

&nbsp;
Example 1:

Input: s = "(abcd)"
Output: "dcba"


Example 2:

Input: s = "(u(love)i)"
Output: "iloveu"
Explanation: The substring "love" is reversed first, then the whole string is reversed.


Example 3:

Input: s = "(ed(et(oc))el)"
Output: "leetcode"
Explanation: First, we reverse the substring "oc", then "etco", and finally, the whole string.


&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 2000
	s only contains lower case English characters and parentheses.
	It is guaranteed that all parentheses are balanced.


class Solution:
    def reverseParentheses(self, s: str) -> str:
        stack = []
        ans = ""
        res = deque([])
        s = list(s)
        for i in s:
            if i==")":
                while stack[-1] != "(":
                    res.append(stack.pop())
                stack.pop()
                while res:
                    stack.append(res.popleft())
            else:
                stack.append(i)
        return "".join(stack)
class Solution {
    public String reverseParentheses(String s) {
        Stack<String> stack = new Stack<>();

        int j = 0;
        while(j < s.length()){
            /*
                We need to keep on adding whatever comes
                as long as it is not a ')'.
            */
            if(s.charAt(j) != ')')
                stack.push(s.charAt(j)+"");

            /*
                Now that we have encountered an ')', its time
                to start popping from top of stack unless we find an opening
                parenthesis

                then we just need to reverse the string formed by popping
                and put it back on stack.

                Try dry running and it will all make sense
            */
            else{
                StringBuilder sb = new StringBuilder();
                while(!stack.isEmpty() && !stack.peek().equals("(")){
                    sb.append(stack.pop());
                }

                stack.pop();
                stack.push(sb.reverse().toString());
            }
            j++;
        }

        /*
            We have our result string in the stack now,
            we just need to pop it and return the reverse of it.
        */
        StringBuilder res = new StringBuilder();
        while(!stack.isEmpty())
            res.append(stack.pop());

        return res.reverse().toString();
    }
}
class Solution {
public:
    string reverseParentheses(string s) {
        stack<int> st;
        for(int i=0;i<s.size();i++)
        {
            if(s[i]=='(')
            {
                st.push(i);
            }
            else if(s[i]==')')
            {
              int strt=st.top();
              strt=strt+1;
              int end=i;
              reverse(s.begin()+strt,s.begin()+end);
              st.pop();
            }
        }
        string ans="";
        for(int i=0;i<s.size();i++)
        {
            if(s[i]=='(' || s[i]==')')
            {
                continue;
            }
            ans+=s[i];
        }
        return ans;
    }
};
function reverse(s){
    return s.split("").reverse().join("");
}

function solve(s,index) {    
    let ans = "";   
    let j = index;
    while(j<s.length)
    {   
        if(s[j] == '(')
        {
            let store = solve(s,j+1);
            ans += store.ans;
            j = store.j;
        }
        else if(s[j] == ')')
            return {ans : reverse(ans),j};          
        else
            ans+=s[j];            
        j++;
    }    
        
    return ans;
}

var reverseParentheses = function(s) {
    return solve(s,0);
};
Reverse Substrings Between Each Pair of Parentheses