Dada una string str que consta de caracteres ( , ) , { , } , [ , ] y ? . La tarea es encontrar el número total de expresiones de paréntesis equilibrados formadas cuando ? se puede reemplazar con cualquiera de los caracteres de paréntesis.
Estos son algunos ejemplos de expresiones de paréntesis equilibrados: {([])} , {()}[{}] etc.
Y expresiones de paréntesis no equilibrados: {[} , {()] , {()}[) etc.
Ejemplos:
Entrada: str = “(?([?)]?}?”
Salida: 3
({([()]]}),()([()]{}) y ([([])]{} ) son las únicas expresiones balanceadas posibles que se pueden generar a partir de la entrada.Entrada: str = “???[???????]????”
Salida: 392202
Acercarse:
- Si n es impar, entonces el resultado siempre será 0 ya que no habrá expresión balanceada posible.
- Si n id es par, cree una array dp para almacenar cálculos previos.
- Llame a una función recursiva con las siguientes operaciones:
- Si el índice inicial> el índice final , devuelve 1 .
- Si dp[start][end] ya se calculó, devuelva dp[start][end] .
- Ejecute un ciclo desde el inicio + 1 hasta el final incrementando en 2 para encontrar su par de corchetes o ‘?’.
- Luego divida la string en dos mitades para verificar las expresiones de paréntesis posteriores adecuadas desde el inicio + 1 hasta i – 1 e i + 1 hasta el final llamando a la función recursiva.
- Si st[inicio] = ‘?’ y st[i] = ‘?’ entonces se pueden formar un total de 3 combinaciones de pares de corchetes, multiplicando así el resultado de la función recursiva por 3 .
- Regresar dp[inicio][fin]
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find number of balanced // bracket expressions possible #include <bits/stdc++.h> using namespace std; typedef long long int lli; // Max string length const int MAX = 300; // Function to check whether index start // and end can form a bracket pair or not int checkFunc(int i, int j, string st) { // Check for brackets ( ) if (st[i] == '(' && st[j] == ')') return 1; if (st[i] == '(' && st[j] == '?') return 1; if (st[i] == '?' && st[j] == ')') return 1; // Check for brackets [ ] if (st[i] == '[' && st[j] == ']') return 1; if (st[i] == '[' && st[j] == '?') return 1; if (st[i] == '?' && st[j] == ']') return 1; // Check for brackets { } if (st[i] == '{' && st[j] == '}') return 1; if (st[i] == '{' && st[j] == '?') return 1; if (st[i] == '?' && st[j] == '}') return 1; return 0; } // Function to find number of // proper bracket expressions int countRec(int start, int end, int dp[][MAX], string st) { int sum = 0; // If starting index is greater // than ending index if (start > end) return 1; // If dp[start][end] has already been computed if (dp[start][end] != -1) return dp[start][end]; lli i, r = 0; // Search for the bracket in from next index for (i = start + 1; i <= end; i += 2) { // If bracket pair is formed, // add number of combination if (checkFunc(start, i, st)) { sum = sum + countRec(start + 1, i - 1, dp, st) * countRec(i + 1, end, dp, st); } // If ? comes then all three bracket // expressions are possible else if (st[start] == '?' && st[i] == '?') { sum = sum + countRec(start + 1, i - 1, dp, st) * countRec(i + 1, end, dp, st) * 3; } } // Return answer return dp[start][end] = sum; } int countWays(string st) { int n = st.length(); // If n is odd, string cannot be balanced if (n % 2 == 1) return 0; int dp[MAX][MAX]; memset(dp, -1, sizeof(dp)); return countRec(0, n - 1, dp, st); } // Driving function int main() { string st = "(?([?)]?}?"; cout << countWays(st); return 0; }
Java
// Java program to find number of balanced // bracket expressions possible class GFG { // Max string length static int MAX = 300; // Function to check whether index start // and end can form a bracket pair or not static int checkFunc(int i, int j, String st) { // Check for brackets ( ) if (st.charAt(i) == '(' && st.charAt(j) == ')') return 1; if (st.charAt(i) == '(' && st.charAt(j) == '?') return 1; if (st.charAt(i) == '?' && st.charAt(j) == ')') return 1; // Check for brackets [ ] if (st.charAt(i) == '[' && st.charAt(j) == ']') return 1; if (st.charAt(i) == '[' && st.charAt(j) == '?') return 1; if (st.charAt(i) == '?' && st.charAt(j) == ']') return 1; // Check for brackets { } if (st.charAt(i) == '{' && st.charAt(j) == '}') return 1; if (st.charAt(i) == '{' && st.charAt(j) == '?') return 1; if (st.charAt(i) == '?' && st.charAt(j) == '}') return 1; return 0; } // Function to find number of // proper bracket expressions static int countRec(int start, int end, int dp[][], String st) { int sum = 0; // If starting index is greater // than ending index if (start > end) return 1; // If dp[start][end] has already been computed if (dp[start][end] != -1) return dp[start][end]; int i, r = 0; // Search for the bracket in from next index for (i = start + 1; i <= end; i += 2) { // If bracket pair is formed, // add number of combination if (checkFunc(start, i, st) == 1) { sum = sum + countRec(start + 1, i - 1, dp, st) * countRec(i + 1, end, dp, st); } // If ? comes then all three bracket // expressions are possible else if (st.charAt(start) == '?' && st.charAt(i) == '?') { sum = sum + countRec(start + 1, i - 1, dp, st) * countRec(i + 1, end, dp, st) * 3; } } // Return answer return dp[start][end] = sum; } static int countWays(String st) { int n = st.length(); // If n is odd, string cannot be balanced if (n % 2 == 1) return 0; int dp[][] = new int[MAX][MAX]; for (int i = 0; i < MAX; i++) for (int j = 0; j < MAX; j++) dp[i][j] = -1; return countRec(0, n - 1, dp, st); } // Driving function public static void main(String[] args) { String st = "(?([?)]?}?"; System.out.println(countWays(st)); } } // This code is contributed by ihritik
Python 3
# Python 3 program to find number of balanced # bracket expressions possible # Max string length MAX = 300 # Function to check whether index start # and end can form a bracket pair or not def checkFunc(i, j, st): # Check for brackets ( ) if (st[i] == '(' and st[j] == ')'): return 1 if (st[i] == '(' and st[j] == '?'): return 1 if (st[i] == '?' and st[j] == ')'): return 1 # Check for brackets [ ] if (st[i] == '[' and st[j] == ']'): return 1 if (st[i] == '[' and st[j] == '?'): return 1 if (st[i] == '?' and st[j] == ']'): return 1 # Check for brackets { } if (st[i] == '{' and st[j] == '}'): return 1 if (st[i] == '{' and st[j] == '?'): return 1 if (st[i] == '?' and st[j] == '}'): return 1 return 0 # Function to find number of # proper bracket expressions def countRec(start, end, dp, st): sum = 0 # If starting index is greater # than ending index if (start > end): return 1 # If dp[start][end] has already # been computed if (dp[start][end] != -1): return dp[start][end] r = 0 # Search for the bracket in from next index for i in range(start + 1, end + 1, 2): # If bracket pair is formed, # add number of combination if (checkFunc(start, i, st)): sum = (sum + countRec(start + 1, i - 1, dp, st) * countRec(i + 1, end, dp, st)) # If ? comes then all three bracket # expressions are possible elif (st[start] == '?' and st[i] == '?'): sum = (sum + countRec(start + 1, i - 1, dp, st) * countRec(i + 1, end, dp, st) * 3) # Return answer dp[start][end] = sum return dp[start][end] def countWays( st): n = len(st) # If n is odd, string cannot be balanced if (n % 2 == 1): return 0 dp = [[-1 for i in range(MAX)] for i in range(MAX)] return countRec(0, n - 1, dp, st) # Driver Code if __name__ =="__main__": st = "(?([?)]?}?" print(countWays(st)) # This code is contributed by ita_c
C#
// C# program to find number of balanced // bracket expressions possible using System; class GFG { // Max string length static int MAX = 300; // Function to check whether index start // and end can form a bracket pair or not static int checkFunc(int i, int j, string st) { // Check for brackets ( ) if (st[i] == '(' && st[j] == ')') return 1; if (st[i] == '(' && st[j] == '?') return 1; if (st[i] == '?' && st[j] == ')') return 1; // Check for brackets [ ] if (st[i] == '[' && st[j] == ']') return 1; if (st[i] == '[' && st[j] == '?') return 1; if (st[i] == '?' && st[j] == ']') return 1; // Check for brackets { } if (st[i] == '{' && st[j] == '}') return 1; if (st[i] == '{' && st[j] == '?') return 1; if (st[i] == '?' && st[j] == '}') return 1; return 0; } // Function to find number of // proper bracket expressions static int countRec(int start, int end, int[, ] dp, string st) { int sum = 0; // If starting index is greater // than ending index if (start > end) return 1; // If dp[start, end] has already been computed if (dp[start, end] != -1) return dp[start, end]; int i; // Search for the bracket in from next index for (i = start + 1; i <= end; i += 2) { // If bracket pair is formed, // add number of combination if (checkFunc(start, i, st) == 1) { sum = sum + countRec(start + 1, i - 1, dp, st) * countRec(i + 1, end, dp, st); } // If ? comes then all three bracket // expressions are possible else if (st[start] == '?' && st[i] == '?') { sum = sum + countRec(start + 1, i - 1, dp, st) * countRec(i + 1, end, dp, st) * 3; } } // Return answer return dp[start, end] = sum; } static int countWays(string st) { int n = st.Length; // If n is odd, string cannot be balanced if (n % 2 == 1) return 0; int[, ] dp = new int[MAX, MAX]; for (int i = 0; i < MAX; i++) for (int j = 0; j < MAX; j++) dp[i, j] = -1; return countRec(0, n - 1, dp, st); } // Driving function public static void Main() { string st = "(?([?)]?}?"; Console.WriteLine(countWays(st)); } } // This code is contributed by ihritik
Javascript
<script> // Javascript program to find number of balanced // bracket expressions possible // Max string length let MAX = 300; // Function to check whether index start // and end can form a bracket pair or not function checkFunc(i,j,st) { // Check for brackets ( ) if (st[i] == '(' && st[j] == ')') return 1; if (st[i] == '(' && st[j] == '?') return 1; if (st[i] == '?' && st[j] == ')') return 1; // Check for brackets [ ] if (st[i] == '[' && st[j] == ']') return 1; if (st[i] == '[' && st[j] == '?') return 1; if (st[i] == '?' && st[j] == ']') return 1; // Check for brackets { } if (st[i] == '{' && st[j] == '}') return 1; if (st[i] == '{' && st[j] == '?') return 1; if (st[i] == '?' && st[j] == '}') return 1; return 0; } // Function to find number of // proper bracket expressions function countRec(start,end,dp,st) { let sum = 0; // If starting index is greater // than ending index if (start > end) return 1; // If dp[start][end] has already been computed if (dp[start][end] != -1) return dp[start][end]; let i, r = 0; // Search for the bracket in from next index for (i = start + 1; i <= end; i += 2) { // If bracket pair is formed, // add number of combination if (checkFunc(start, i, st) == 1) { sum = sum + countRec(start + 1, i - 1, dp, st) * countRec(i + 1, end, dp, st); } // If ? comes then all three bracket // expressions are possible else if (st[start] == '?' && st[i] == '?') { sum = sum + countRec(start + 1, i - 1, dp, st) * countRec(i + 1, end, dp, st) * 3; } } // Return answer return dp[start][end] = sum; } function countWays(st) { let n = st.length; // If n is odd, string cannot be balanced if (n % 2 == 1) return 0; let dp = new Array(MAX); for (let i = 0; i < MAX; i++) { dp[i]=new Array(MAX); for (let j = 0; j < MAX; j++) dp[i][j] = -1; } return countRec(0, n - 1, dp, st); } // Driving function let st = "(?([?)]?}?"; document.write(countWays(st)); // This code is contributed by rag2127 </script>
Producción:
3