Substrings inversas entre cada par de paréntesis

Dada una string str que consiste en letras minúsculas en inglés y corchetes. La tarea es invertir las substrings en cada par de paréntesis coincidentes, comenzando desde el más interno. El resultado no debe contener corchetes.

Ejemplos:  

Entrada: str = “(skeeg(for)skeeg)” 
Salida: geeksforgeeks

Entrada: str = “((ng)ipm(ca))” 
Salida: acampar 

Enfoque: Este problema se puede resolver usando una pila . Primero, cada vez que se encuentre un ‘(‘ , inserte el índice del elemento en la pila, y cada vez que se encuentre un ‘)’ , obtenga el elemento superior de la pila como el índice más reciente e invierta la string entre el índice actual y el índice desde la parte superior de la pila. Siga esto para el resto de la string y finalmente imprima la string actualizada.

A continuación se muestra la implementación del enfoque anterior:  

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the modified string
string reverseParentheses(string str, int len)
{
    stack<int> st;
 
    for (int i = 0; i < len; i++) {
 
        // Push the index of the current
        // opening bracket
        if (str[i] == '(') {
            st.push(i);
        }
 
        // Reverse the substring starting
        // after the last encountered opening
        // bracket till the current character
        else if (str[i] == ')') {
            reverse(str.begin() + st.top() + 1,
                    str.begin() + i);
            st.pop();
        }
    }
 
    // To store the modified string
    string res = "";
    for (int i = 0; i < len; i++) {
        if (str[i] != ')' && str[i] != '(')
            res += (str[i]);
    }
    return res;
}
 
// Driver code
int main()
{
    string str = "(skeeg(for)skeeg)";
    int len = str.length();
 
    cout << reverseParentheses(str, len);
 
    return 0;
}

// Java implementation of the approach
import java.io.*;
import java.util.*;
class GFG {
  static void reverse(char A[], int l, int h)
  {
    if (l < h)
    {
      char ch = A[l];
      A[l] = A[h];
      A[h] = ch;
      reverse(A, l + 1, h - 1);
    }
  }
   
  // Function to return the modified string
  static String reverseParentheses(String str, int len)
  {
    Stack<Integer> st = new Stack<Integer>();
    for (int i = 0; i < len; i++)
    {
       
      // Push the index of the current
      // opening bracket
      if (str.charAt(i) == '(')
      {
        st.push(i);
      }
       
      // Reverse the substring starting
      // after the last encountered opening
      // bracket till the current character
      else if (str.charAt(i) == ')')
      {
        char[] A = str.toCharArray();
        reverse(A, st.peek() + 1, i);
        str = String.copyValueOf(A);
        st.pop();
      }
    }
     
    // To store the modified string
    String res = "";
    for (int i = 0; i < len; i++)
    {
      if (str.charAt(i) != ')' && str.charAt(i) != '(')
      {
        res += (str.charAt(i));
      }
    }
    return res;
  }
 
  // Driver code
  public static void main (String[] args)
  {
    String str = "(skeeg(for)skeeg)";
    int len = str.length();
    System.out.println(reverseParentheses(str, len));
  }
}
 
// This code is contributed by avanitrachhadiya2155

# Python3 implementation of the approach
 
# Function to return the modified string
def reverseParentheses(strr, lenn):
    st = []
 
    for i in range(lenn):
 
        # Push the index of the current
        # opening bracket
        if (strr[i] == '('):
            st.append(i)
 
        # Reverse the substring starting
        # after the last encountered opening
        # bracket till the current character
        else if (strr[i] == ')'):
            temp = strr[st[-1]:i + 1]
            strr = strr[:st[-1]] + temp[::-1] + \
                   strr[i + 1:]
            del st[-1]
 
    # To store the modified string
    res = ""
    for i in range(lenn):
        if (strr[i] != ')' and strr[i] != '('):
            res += (strr[i])
    return res
 
# Driver code
if __name__ == '__main__':
    strr = "(skeeg(for)skeeg)"
    lenn = len(strr)
    st = [i for i in strr]
 
    print(reverseParentheses(strr, lenn))
 
# This code is contributed by Mohit Kumar

// C# implementation of the approach
using System;
using System.Collections.Generic;
using System.Text;
 
class GFG{
     
static void reverse(char[] A, int l, int h)
{
    if (l < h)
    {
        char ch = A[l];
        A[l] = A[h];
        A[h] = ch;
        reverse(A, l + 1, h - 1);
    }
}
 
// Function to return the modified string
static string reverseParentheses(string str, int len)
{
    Stack<int> st = new Stack<int>();
     
    for(int i = 0; i < len; i++)
    {
         
        // Push the index of the current
        // opening bracket
        if (str[i] == '(')
        {
            st.Push(i);
        }
         
        // Reverse the substring starting
        // after the last encountered opening
        // bracket till the current character
        else if (str[i] == ')')
        {
            char[] A = str.ToCharArray();
            reverse(A, st.Peek() + 1, i);
            str = new string(A);
            st.Pop();
        }
    }
     
    // To store the modified string
    string res = "";
    for(int i = 0; i < len; i++)
    {
        if (str[i] != ')' && str[i] != '(')
        {
            res += str[i];
        }
    }
    return res;
}
 
// Driver code
static public void Main()
{
    string str = "(skeeg(for)skeeg)";
    int len = str.Length;
     
    Console.WriteLine(reverseParentheses(str, len));
}
}
 
// This code is contributed by rag2127

<script>
// Javascript implementation of the approach
function reverse(A,l,h)
{
    if (l < h)
    {
      let ch = A[l];
      A[l] = A[h];
      A[h] = ch;
      reverse(A, l + 1, h - 1);
    }
}
 
 // Function to return the modified string
function reverseParentheses(str,len)
{
    let st = [];
    for (let i = 0; i < len; i++)
    {
        
      // Push the index of the current
      // opening bracket
      if (str[i] == '(')
      {
        st.push(i);
      }
        
      // Reverse the substring starting
      // after the last encountered opening
      // bracket till the current character
      else if (str[i] == ')')
      {
           
        let A = [...str]
        reverse(A, st[st.length-1] + 1, i);
        str = [...A];
        st.pop();
      }
    }
      
    // To store the modified string
    let res = "";
    for (let i = 0; i < len; i++)
    {
      if (str[i] != ')' && str[i] != '(')
      {
        res += (str[i]);
      }
    }
    return res;
}
 
 // Driver code
let str = "(skeeg(for)skeeg)";
let len = str.length;
document.write(reverseParentheses(str, len));
 
// This code is contributed by patel2127
</script>

geeksforgeeks