Dada una string str que contiene los caracteres ‘(‘ , ‘)’ , ‘{‘ , ‘}’ , ‘[‘ y ‘]’ , la tarea es determinar si los paréntesis están equilibrados o no. Los paréntesis están balanceados si:
- Los corchetes abiertos deben cerrarse con el mismo tipo de corchetes.
- Los corchetes abiertos deben cerrarse en el orden correcto.
Ejemplos:
Entrada: str = “(())[]” Salida: Sí Entrada: str = “))(({}{” Salida: No
Acercarse:
- Mantenga dos variables i y j para realizar un seguimiento de los dos corchetes que se van a comparar.
- Mantenga un recuento cuyo valor aumente al encontrar un paréntesis de apertura y disminuya al encontrar un paréntesis de cierre.
- Establezca j = i , i = i + 1 y counter++ cuando se encuentren corchetes de apertura.
- Cuando se encuentran corchetes de cierre, disminuya el conteo y compare los corchetes en i y j ,
- Si los corchetes en i y j coinciden, entonces sustituya ‘#’ en la string en la i -ésima y j -ésima posición. Incremente i y disminuya j hasta que se encuentre un valor que no sea ‘#’ o j ≥ 0 .
- Si los corchetes en i y j no coinciden, devuelve falso.
- Si cuenta != 0 , devuelve falso.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <iostream>
using namespace std;
// This helper function is called whenever
// closing bracket is encountered.
// Hence count is decremented
// j and i points to opening and closing
// brackets to be matched respectively
// If brackets at i and j is a match
// replace them with "#" character and decrement j
// to point next opening bracket to * be matched
// Similarly, increment i to point to next closing
// bracket to be matched
// If j is out of bound or brackets did not match return 0
bool helperFunc(int& count, string& s, int& i, int& j, char tocom)
{
count--;
if (j > -1 && s[j] == tocom) {
s[i] = '#';
s[j] = '#';
while (j >= 0 && s[j] == '#')
j--;
i++;
return 1;
}
else
return 0;
}
// Function that returns true if s is a
// valid balanced bracket string
bool isValid(string s)
{
// Empty string is considered balanced
if (s.length() == 0)
return true;
else {
int i = 0;
// Increments for opening bracket and
// decrements for closing bracket
int count = 0;
int j = -1;
bool result;
while (i < s.length()) {
switch (s[i]) {
case '}':
result = helperFunc(count, s, i, j, '{');
if (result == 0) {
return false;
}
break;
case ')':
result = helperFunc(count, s, i, j, '(');
if (result == 0) {
return false;
}
break;
case ']':
result = helperFunc(count, s, i, j, '[');
if (result == 0) {
return false;
}
break;
default:
j = i;
i++;
count++;
}
}
// count != 0 indicates unbalanced parentheses
// this check is required to handle cases where
// count of opening brackets > closing brackets
if (count != 0)
return false;
return true;
}
}
// Driver code
int main()
{
string str = "[[]][]()";
if (isValid(str))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
static String s = "[[]][]()";
static int count = 0;
static int i = 0;
static int j = -1;
// This helper function is called whenever
// closing bracket is encountered.
// Hence count is decremented
// j and i points to opening and closing
// brackets to be matched respectively
// If brackets at i and j is a match
// replace them with "#" character and decrement j
// to point next opening bracket to * be matched
// Similarly, increment i to point to next closing
// bracket to be matched
// If j is out of bound or brackets did not match return 0
static int helperFunc(char tocom)
{
count--;
char temp = s.charAt(j);
if (j > -1 && temp == tocom)
{
s = s.replace(s.charAt(i),'#');
s = s.replace(s.charAt(j),'#');
temp = s.charAt(j);
while (j >= 0 && temp == '#')
j--;
i++;
return 1;
}
else
return 0;
}
// Function that returns true if s is a
// valid balanced bracket string
static boolean isValid()
{
// Empty string is considered balanced
if (s.length() == 0)
return true;
else {
int result;
while (i < s.length())
{
char temp = s.charAt(i);
if(temp=='}')
{
result = helperFunc('{');
if (result == 0)
{
return false;
}
}
else if(temp == ')')
{
result = helperFunc('(');
if (result == 0)
{
return false;
}
}
else if(temp == ']')
{
result = helperFunc('[');
if (result == 0)
{
return false;
}
}
else
{
j = i;
i++;
count++;
}
}
// count != 0 indicates unbalanced parentheses
// this check is required to handle cases where
// count of opening brackets > closing brackets
if (count != 0)
return false;
return true;
}
}
// Driver code
public static void main(String args[])
{
if (isValid())
System.out.println("No");
else
System.out.println("Yes");
}
}
// This code is contributed by Surendra_Gangwar
Python3
# Python3 implementation of the approach
# These are defined as global because they
# are passed by reference
count = 0
i = 0
j = -1
# This helper function is called whenever
# closing bracket is encountered.
# Hence count is decremented
# j and i points to opening and closing
# brackets to be matched respectively
# If brackets at i and j is a match
# replace them with "#" character and decrement j
# to point next opening bracket to * be matched
# Similarly, increment i to point to next closing
# bracket to be matched
# If j is out of bound or brackets
# did not match return 0
def helperFunc(s, tocom):
global i, j, count
count -= 1
if j > -1 and s[j] == tocom:
s[i] = '#'
s[j] = '#'
while j >= 0 and s[j] == '#':
j -= 1
i += 1
return 1
else:
return 0
# Function that returns true if s is a
# valid balanced bracket string
def isValid(s):
global i, j, count
# Empty string is considered balanced
if len(s) == 0:
return True
else:
# Increments for opening bracket and
# decrements for closing bracket
result = False
while i < len(s):
if s[i] == '}':
result = helperFunc(s, '{')
if result == 0:
return False
elif s[i] == ')':
result = helperFunc(s, '(')
if result == 0:
return False
elif s[i] == ']':
result = helperFunc(s, '[')
if result == 0:
return False
else:
j = i
i += 1
count += 1
# count != 0 indicates unbalanced parentheses
# this check is required to handle cases where
# count of opening brackets > closing brackets
if count != 0:
return False
return True
# Driver Code
if __name__ == "__main__":
string = "[[]][]()"
string = list(string)
print("Yes") if isValid(string) else print("No")
# This code is contributed by
# sanjeev2552
C#
// C# implementation of the approach
using System;
class GFG{
static string s = "[[]][]()";
static int count = 0;
static int i = 0;
static int j = -1;
// This helper function is called whenever
// closing bracket is encountered. Hence
// count is decremented j and i points to
// opening and closing brackets to be matched
// respectively. If brackets at i and j is a match
// replace them with "#" character and decrement j
// to point next opening bracket to * be matched
// Similarly, increment i to point to next closing
// bracket to be matched. If j is out of bound or
// brackets did not match return 0
static int helperFunc(char tocom)
{
count--;
char temp = s[j];
if (j > -1 && temp == tocom)
{
s = s.Replace(s[i],'#');
s = s.Replace(s[j],'#');
temp = s[j];
while (j >= 0 && temp == '#')
j--;
i++;
return 1;
}
else
return 0;
}
// Function that returns true if s is a
// valid balanced bracket string
static bool isValid()
{
// Empty string is considered balanced
if (s.Length == 0)
return true;
else
{
int result;
while (i < s.Length)
{
char temp = s[i];
if(temp == '}')
{
result = helperFunc('{');
if (result == 0)
{
return false;
}
}
else if(temp == ')')
{
result = helperFunc('(');
if (result == 0)
{
return false;
}
}
else if(temp == ']')
{
result = helperFunc('[');
if (result == 0)
{
return false;
}
}
else
{
j = i;
i++;
count++;
}
}
// count != 0 indicates unbalanced
// parentheses this check is required
// to handle cases where count of opening
// brackets > closing brackets
if (count != 0)
return false;
return true;
}
}
// Driver code
public static void Main(string []args)
{
if (isValid())
{
Console.Write("No");
}
else
{
Console.Write("Yes");
}
}
}
// This code is contributed by rutvik_56
Producción:
Yes
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por GarimaDhaka y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA