# https://leetcode.com/problems/reverse-substrings-between-each-pair-of-parentheses/
# 1190. Reverse Substrings Between Each Pair of Parentheses

# History:
# Cruise
# 1.
# May 17, 2020

# 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.
#
#
#
# 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.
# Example 4:
#
# Input: s = "a(bcdefghijkl(mno)p)q"
# Output: "apmnolkjihgfedcbq"
#
#
# Constraints:
#
# 0 <= s.length <= 2000
# s only contains lower case English characters and parentheses.
# It's guaranteed that all parentheses are balanced.


class Solution(object):
    def reverseParentheses(self, s):
        """
        :type s: str
        :rtype: str
        """
        stack = []

        for c in s:
            if c == '(' or c.isalpha():
                stack.append(c)
            else:
                s = []
                while stack[-1] != '(':
                    s.append(stack.pop(-1))

                stack.pop(-1)
                stack.extend(s)

        return "".join(stack)
