Calcule el peso del paréntesis en función de las condiciones dadas

Dada una string de paréntesis válida S , la tarea es encontrar el peso del paréntesis en función de las siguientes condiciones:  

  1. El peso de “( )” es 1
  2. Peso de «AB» = peso de «A» + peso de «B» (donde A y B son paréntesis válidos independientes). por ejemplo, peso de “()()” = peso de “()” + peso de “()”
  3. Peso de “(A)” = 2 veces el peso de “A” (donde A es un paréntesis válido independiente). por ejemplo, el peso de «(())» es 2 veces el peso de «()»

Ejemplos:  

Entrada: S = “()(())” 
Salida:
Explicación: 
Peso de() = 1 
Peso de (()) = 2 
Por lo tanto, el peso de()(()) = 1 + 2 = 3

Entrada: S = “(()(()))” 
Salida:
Explicación: 
Peso de()(()) = 3 
Peso de (()(())) = 2 * 3 = 6 
 

Enfoque: 
Este problema se puede resolver utilizando el enfoque Divide y vencerás . Siga los pasos a continuación para resolver el problema: 
 

  • Se da que la string de paréntesis de entrada es siempre válida, es decir, equilibrada. Entonces, cualquier corchete de apertura ‘(‘ tiene un corchete de cierre correspondiente ‘)’ .
  • Considere el corchete de apertura al comienzo de la string de entrada (el corchete de inicio no puede ser un corchete de cierre, de lo contrario no será válido). Ahora bien, para este paréntesis de apertura, el paréntesis de cierre correspondiente puede tener cualquiera de los siguientes dos índices posibles. 
    1. Al final, es decir , (n-1) th index
    2. En algún lugar entre el principio y el final , es decir , [1, n-2]
  • Si el corchete de cierre tiene un índice al final, entonces de acuerdo con la restricción no. 3, el peso total del paréntesis será el doble del peso de string[1, n-2] . 
     
  • Si el paréntesis de cierre se encuentra en algún lugar entre el inicio y el final, digamos a la mitad, entonces de acuerdo con la restricción no. 2, el peso total del paréntesis será la suma del peso de string[start, mid] y la suma del peso de string[mid+1, end]
     
  • El caso base para nuestra recursividad será cuando tengamos solo dos corchetes en la string, tendrán un peso de 1 porque inherentemente serán válidos. 
     
  • Ahora, la pregunta es cómo podemos encontrar el índice del paréntesis de cierre correspondiente para un paréntesis de apertura. La idea es similar a la comprobación de paréntesis válida . Usaremos la estructura de datos de pila para verificar y almacenar el índice del corchete de cierre para el corchete de apertura correspondiente en un HashMap
     
  • Realice los siguientes pasos: 
    • Atraviesa la cuerda.
    • Si un carácter es un corchete de apertura, inserte su índice en la pila .
    • Si es un paréntesis de cierre, extraiga su índice de la pila e inserte el emparejamiento (popped_index, current_index) en el HashMap .

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

C++

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// HashMap to store the ending
// index of every opening bracket
unordered_map<int, int> endIndex;
 
// Function to calculate and store
// the closing index of each opening
// bracket in the parenthesis
void getClosingIndex(string s)
{
    int n = s.length();
 
    stack<int> st;
 
    for(int i = 0; i < n; i++)
    {
        if (s[i] == ')')
        {
             
            // If it's a closing bracket,
            // pop index of it's corresponding
            // opening bracket
            int startIndex = st.top();
            st.pop();
             
            // Insert the index of opening
            // bracket and closing bracket
            // as key-value pair in the
            // hashmap
            endIndex[startIndex] = i;
        }
        else
        {
             
            // If it's an opening bracket,
            // push it's index into the stack
            st.push(i);
        }
    }
}
 
// Function to return the weight of
// parenthesis
int calcWeight(string s, int low, int high)
{
     
    // Base case
    if (low + 1 == high)
    {
        return 1;
    }
 
    else
    {
 
        // Mid refers to ending index of
        // opening bracket at index low
        int mid = endIndex[low];
         
        if (mid == high)
        {
            return 2 * calcWeight(s, low + 1,
                                    high - 1);
        }
        else
        {
            return calcWeight(s, low, mid) +
                   calcWeight(s, mid + 1,
                              high);
        }
    }
}
 
// Driver Code
int main()
{
    string input = "(()(()))";
    int n = input.length();
 
    // Update the closing Index
    getClosingIndex(input);
 
    cout << (calcWeight(input, 0, n - 1)) << endl;
 
    return 0;
}
 
// This code is contributed by divyeshrabadiya07

Java

// Java Program to implement
// the above approach
import java.util.*;
 
public class GFG {
 
    // HashMap to store the ending
    // index of every opening bracket
    static HashMap<Integer, Integer> endIndex
        = new HashMap<Integer, Integer>();
 
    // Function to calculate and store
    // the closing index of each opening
    // bracket in the parenthesis
    public static void getClosingIndex(String s)
    {
 
        int n = s.length();
 
        Stack<Integer> st = new Stack<Integer>();
 
        for (int i = 0; i < n; i++) {
 
            if (s.charAt(i) == ')') {
 
                // If it's a closing bracket,
                // pop index of it's corresponding
                // opening bracket
                int startIndex = st.pop();
 
                // Insert the index of opening
                // bracket and closing bracket
                // as key-value pair in the
                // hashmap
                endIndex.put(startIndex, i);
            }
            else {
 
                // If it's an opening bracket,
                // push it's index into the stack
                st.push(i);
            }
        }
    }
 
    // Function to return the weight of
    // parenthesis
    public static int calcWeight(String s,
                                int low,
                                int high)
    {
 
        // Base case
        if (low + 1 == high) {
            return 1;
        }
 
        else {
 
            // Mid refers to ending index of
            // opening bracket at index low
            int mid = endIndex.get(low);
            if (mid == high) {
                return 2 * calcWeight(s, low + 1,
                                    high - 1);
            }
            else {
                return calcWeight(s, low, mid)
                    + calcWeight(s, mid + 1,
                                high);
            }
        }
    }
 
    public static void main(String[] args)
    {
        String input = "(()(()))";
        int n = input.length();
 
        // Update the closing Index
        getClosingIndex(input);
 
        System.out.println(calcWeight(input,
                                    0, n - 1));
    }
}

Python3

# Python3 program to implement the
# above approach
 
# Function to calculate and store
# the closing index of each opening
# bracket in the parenthesis
def getClosingIndex(string):
 
    # Dictionary to store
    # the ending index of
    # each opening bracket
    endIndex = dict()
 
 
    n = len(string)
 
    stack = []
    for i in range(n):
        if (string[i]==')'):
 
            # If it's a closing bracket,
            # pop index of it's
            # corresponding
            # opening bracket
            startIndex = stack.pop()
 
            # Put the index of opening
            # bracket and closing
            # bracket as key value
            # pair in the Dictionary
            endIndex[startIndex] = i
 
        else:
 
            # If it's an opening bracket,
            # push it's index into
            # the stack
            stack.append(i)
    return endIndex
     
# Function to return the weight
# of parenthesis
def calcWeight(s, low,
                high, endIndex):
 
 
    # Base case
    if (low + 1 == high):
        return 1
    else:
 
        # Mid refers to ending index of
        # opening bracket at index low
        mid = endIndex[low]
        if (mid == high):
            return 2*(calcWeight(s, low + 1,
            high-1, endIndex))
 
        else:
            return calcWeight(s, low,
            mid, endIndex) + calcWeight(s,
            mid + 1, high, endIndex)
 
 
if __name__ == "__main__":
    string = "(()(()))"
    n = len(string)
    endIndex = getClosingIndex(string)
    print(calcWeight(string, 0,
    n-1, endIndex))

C#

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// HashMap to store the ending
// index of every opening bracket
static Dictionary<int,
                  int> endIndex = new Dictionary<int,
                                                 int>();
 
// Function to calculate and store
// the closing index of each opening
// bracket in the parenthesis
public static void getClosingIndex(string s)
{
    int n = s.Length;
 
    Stack<int> st = new Stack<int>();
 
    for(int i = 0; i < n; i++)
    {
        if (s[i] == ')')
        {
             
            // If it's a closing bracket,
            // pop index of it's corresponding
            // opening bracket
            int startIndex = st.Pop();
 
            // Insert the index of opening
            // bracket and closing bracket
            // as key-value pair in the
            // hashmap
            endIndex.Add(startIndex, i);
        }
        else
        {
 
            // If it's an opening bracket,
            // push it's index into the stack
            st.Push(i);
        }
    }
}
 
// Function to return the weight of
// parenthesis
public static int calcWeight(string s, int low,
                                       int high)
{
 
    // Base case
    if (low + 1 == high)
    {
        return 1;
    }
    else
    {
         
        // Mid refers to ending index of
        // opening bracket at index low
        int mid = endIndex[low];
        if (mid == high)
        {
            return 2 * calcWeight(s, low + 1,
                                    high - 1);
        }
        else
        {
            return calcWeight(s, low, mid) +
                   calcWeight(s, mid + 1, high);
        }
    }
}
 
// Driver code
public static void Main(string[] args)
{
    string input = "(()(()))";
    int n = input.Length;
 
    // Update the closing Index
    getClosingIndex(input);
 
    Console.Write(calcWeight(input, 0, n - 1));
}
}
 
// This code is contributed by rutvik_56

Javascript

<script>
 
// Javascript program to implement
// the above approach
 
// HashMap to store the ending
// index of every opening bracket
var endIndex = new Map();
 
// Function to calculate and store
// the closing index of each opening
// bracket in the parenthesis
function getClosingIndex(s)
{
    var n = s.length;
 
    var st = [];
 
    for(var i = 0; i < n; i++)
    {
        if (s[i] == ')')
        {
             
            // If it's a closing bracket,
            // pop index of it's corresponding
            // opening bracket
            var startIndex = st[st.length-1];
            st.pop();
             
            // Insert the index of opening
            // bracket and closing bracket
            // as key-value pair in the
            // hashmap
            endIndex[startIndex] = i;
        }
        else
        {
             
            // If it's an opening bracket,
            // push it's index into the stack
            st.push(i);
        }
    }
}
 
// Function to return the weight of
// parenthesis
function calcWeight(s, low, high)
{
     
    // Base case
    if (low + 1 == high)
    {
        return 1;
    }
 
    else
    {
 
        // Mid refers to ending index of
        // opening bracket at index low
        var mid = endIndex[low];
         
        if (mid == high)
        {
            return 2 * calcWeight(s, low + 1,
                                    high - 1);
        }
        else
        {
            return calcWeight(s, low, mid) +
                   calcWeight(s, mid + 1,
                              high);
        }
    }
}
 
// Driver Code
var input = "(()(()))";
var n = input.length;
// Update the closing Index
getClosingIndex(input);
document.write((calcWeight(input, 0, n - 1)));
 
 
</script>
Producción: 

6

 

Complejidad de tiempo: O(N) 
Espacio auxiliar: O(N), donde N es la longitud de la string.
 

Publicación traducida automáticamente

Artículo escrito por jigyansu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *