Dada una string str que consta de paréntesis de [ “(” , “)” , “{” , “}” , “[” , “]” ].
Si la string está perfectamente equilibrada, devuelve 0; de lo contrario, devuelve el índice (a partir de 1) en el que se encuentra que el anidamiento es incorrecto.
Ejemplos:
Entrada: str = “{[()]}[]”
Salida: 0
Entrada: str = “[{]()}”
Salida: 3
Entrada: str = “}[{}]”
Salida: 1
Entrada: str = «{([]){»
Salida: 7
Acercarse:
- Primero estamos creando el lst1 y lst2 que tendrán los paréntesis de apertura y cierre respectivamente
- Ahora crearemos otra lista lst que funcionará como una pila , lo que significa que si aparecen corchetes de cierre en la string, se eliminarán los respectivos corchetes de apertura presentes en la lista.
- Si aparecen corchetes de cierre en la string y no hay corchetes de apertura respectivos en el primero, entonces este será el índice incorrecto, lo devolveremos.
- Si llegamos al final de la string mientras la recorremos y el tamaño de la lista no es igual a 0, devolveremos len(String)+1
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
int main()
{
// Defining the string
string String = "{[()]}[]";
// Storing opening braces in list lst1
vector<char> lst1 ={'{', '(', '['};
// Storing closing braces in list lst2
vector<char> lst2 ={'}', ')', ']'};
// Creating an empty list lst
vector<char> lst;
int k;
// Creating dictionary to map
// closing braces to opening ones
map<char,char> Dict;
Dict.insert(pair<int, int>(')', '('));
Dict.insert(pair<int, int>('}', '{'));
Dict.insert(pair<int, int>(']', '['));
int a = 0, b = 0, c = 0;
// If first position of string contain
// any closing braces return 1
if(count(lst2.begin(), lst2.end(), String[0]))
{
cout << 1 << endl;
}
else
{
// If characters of string are opening
// braces then append them in a list
for(int i = 0; i < String.size(); i++)
{
if(count(lst1.begin(), lst1.end(), String[i]))
{
lst.push_back(String[i]);
k = i + 2;
}
else
{
// When size of list is 0 and new closing
// braces is encountered then print its
// index starting from 1
if(lst.size()== 0 && (count(lst2.begin(), lst2.end(), String[i])))
{
cout << (i + 1) << endl;
c = 1;
break;
}
else
{
// As we encounter closing braces we map
// them with theircorresponding opening
// braces using dictionary and check
// if it is same as last opened braces
//(last element in list) if yes then we
// delete that element from list
if(Dict[String[i]]== lst[lst.size()-1])
{
lst.pop_back();
}
else
{
// Otherwise we return the index
// (starting from 1) at which
// nesting is found wrong
break;
cout << (i + 1) << endl;
a = 1;
}
}
}
}
// At end if the list is empty it
// means the string is perfectly nested
if(lst.size() == 0 && c == 0)
{
cout << 0 << endl;
b = 1;
}
if(a == 0 && b == 0 && c == 0)
{
cout << k << endl;
}
}
return 0;
}
// This code is contributed by decode2207.
Java
// Java implementation of the approach
import java.util.*;
public class Main
{
public static void main(String[] args)
{
// Defining the string
String string = "{[()]}[]";
// Storing opening braces in list lst1
char[] lst1 = {'{', '(', '['};
// Storing closing braces in list lst2
char[] lst2 = {'}', ')', ']'};
// Creating an empty list lst
Vector<Character> lst = new Vector<Character>();
// Creating dictionary to map
// closing braces to opening ones
HashMap<Character, Character> Dict = new HashMap<>();
Dict.put(')', '(');
Dict.put('}', '{');
Dict.put(']', '[');
int a = 0, b = 0, c = 0;
// If first position of string contain
// any closing braces return 1
if(Arrays.asList(lst2).contains(string.charAt(0)))
{
System.out.println(1);
}
else
{
int k = 0;
// If characters of string are opening
// braces then append them in a list
for(int i = 0; i < string.length(); i++)
{
if(Arrays.asList(lst1).contains(string.charAt(i)))
{
lst.add(string.charAt(i));
k = i + 2;
}
else
{
// When size of list is 0 and new closing
// braces is encountered then print its
// index starting from 1
if(lst.size()== 0 && Arrays.asList(lst2).contains(string.charAt(i)))
{
System.out.println((i + 1));
c = 1;
break;
}
else
{
// As we encounter closing braces we map
// them with theircorresponding opening
// braces using dictionary and check
// if it is same as last opened braces
//(last element in list) if yes then we
// delete that element from list
if(lst.size() > 0 && Dict.get(string.charAt(i))== lst.get(lst.size() - 1))
{
lst.remove(lst.size() - 1);
}
else
{
// Otherwise we return the index
// (starting from 1) at which
// nesting is found wrong
a = 1;
break;
}
}
}
}
// At end if the list is empty it
// means the string is perfectly nested
if(lst.size() == 0 && c == 0)
{
System.out.println(0);
b = 1;
}
if(a == 0 && b == 0 && c == 0)
{
System.out.println(k);
}
}
}
}
// This code is contributed by divyesh072019.
Python3
# Write Python3 code here
# Defining the string
string = "{[()]}[]"
# Storing opening braces in list lst1
lst1 =['{', '(', '[']
# Storing closing braces in list lst2
lst2 =['}', ')', ']']
# Creating an empty list lst
lst =[]
# Creating dictionary to map
# closing braces to opening ones
Dict ={ ')':'(', '}':'{', ']':'['}
a = b = c = 0
# If first position of string contain
# any closing braces return 1
if string[0] in lst2:
print(1)
else:
# If characters of string are opening
# braces then append them in a list
for i in range(0, len(string)):
if string[i] in lst1:
lst.append(string[i])
k = i + 2
else:
# When size of list is 0 and new closing
# braces is encountered then print its
# index starting from 1
if len(lst)== 0 and (string[i] in lst2):
print(i + 1)
c = 1
break
else:
# As we encounter closing braces we map
# them with theircorresponding opening
# braces using dictionary and check
# if it is same as last opened braces
#(last element in list) if yes then we
# delete that element from list
if Dict[string[i]]== lst[len(lst)-1]:
lst.pop()
else:
# Otherwise we return the index
# (starting from 1) at which
# nesting is found wrong
print(i + 1)
a = 1
break
# At end if the list is empty it
# means the string is perfectly nested
if len(lst)== 0 and c == 0:
print(0)
b = 1
if a == 0 and b == 0 and c == 0:
print(k)
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
static void Main()
{
// Defining the string
string String = "{[()]}[]";
// Storing opening braces in list lst1
char[] lst1 = {'{', '(', '['};
// Storing closing braces in list lst2
char[] lst2 = {'}', ')', ']'};
// Creating an empty list lst
List<char> lst = new List<char>();
// Creating dictionary to map
// closing braces to opening ones
Dictionary<char, char> Dict = new Dictionary<char, char>();
Dict[')'] = '(';
Dict['}'] = '{';
Dict[']'] = '[';
int a = 0, b = 0, c = 0;
// If first position of string contain
// any closing braces return 1
if(Array.Exists(lst2, element => element == String[0]))
{
Console.WriteLine(1);
}
else
{
int k = 0;
// If characters of string are opening
// braces then append them in a list
for(int i = 0; i < String.Length; i++)
{
if(Array.Exists(lst1, element => element == String[i]))
{
lst.Add(String[i]);
k = i + 2;
}
else
{
// When size of list is 0 and new closing
// braces is encountered then print its
// index starting from 1
if(lst.Count== 0 && Array.Exists(lst2, element => element == String[i]))
{
Console.WriteLine((i + 1));
c = 1;
break;
}
else
{
// As we encounter closing braces we map
// them with theircorresponding opening
// braces using dictionary and check
// if it is same as last opened braces
//(last element in list) if yes then we
// delete that element from list
if(lst.Count > 0 && Dict[String[i]]== lst[lst.Count - 1])
{
lst.RemoveAt(lst.Count - 1);
}
else
{
// Otherwise we return the index
// (starting from 1) at which
// nesting is found wrong
a = 1;
break;
}
}
}
}
// At end if the list is empty it
// means the string is perfectly nested
if(lst.Count == 0 && c == 0)
{
Console.WriteLine(0);
b = 1;
}
if(a == 0 && b == 0 && c == 0)
{
Console.WriteLine(k);
}
}
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// Javascript implementation of the approach
// Defining the string
let string = "{[()]}[]";
// Storing opening braces in list lst1
let lst1 =['{', '(', '['];
// Storing closing braces in list lst2
let lst2 =['}', ')', ']'];
// Creating an empty list lst
let lst =[];
// Creating dictionary to map
// closing braces to opening ones
let Dict ={ ')':'(', '}':'{', ']':'['}
let a = 0, b = 0, c = 0;
// If first position of string contain
// any closing braces return 1
if(string[0] in lst2)
{
document.write(1 + "</br>");
}
else
{
// If characters of string are opening
// braces then append them in a list
for(let i = 0; i < string.length; i++)
{
if(string[i] in lst1)
{
lst.push(string[i]);
k = i + 2;
}
else
{
// When size of list is 0 and new closing
// braces is encountered then print its
// index starting from 1
if(lst.length== 0 && (string[i] in lst2))
{
document.write((i + 1) + "</br>");
c = 1;
break;
}
else
{
// As we encounter closing braces we map
// them with theircorresponding opening
// braces using dictionary and check
// if it is same as last opened braces
//(last element in list) if yes then we
// delete that element from list
if(Dict[string[i]]== lst[lst.length-1])
{
lst.pop();
}
else
{
// Otherwise we return the index
// (starting from 1) at which
// nesting is found wrong
break;
document.write((i + 1) + "</br>");
a = 1;
}
}
}
}
// At end if the list is empty it
// means the string is perfectly nested
if(lst.length == 0 && c == 0)
{
document.write(0 + "</br>");
b = 1;
}
if(a == 0 && b == 0 && c == 0)
{
document.write(k + "</br>");
}
}
// This code is contributed by rameshtravel07.
</script>
Producción:
0
Publicación traducida automáticamente
Artículo escrito por hariomagarwal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA