algorithm - signos - operaciones con parentesis corchetes y llaves

¿Cómo encontrar la validez de una cadena de paréntesis, llaves y corchetes?

Question

Recientemente me puse en contacto con este interesante problema. Te dan una cadena que contiene solo los caracteres ''('' , '')'' , ''{'' , ''}'' , ''['' y '']'' , por ejemplo, "[{()}]" , necesitas escribir un función que verificará la validez de dicha cadena de entrada, la función puede ser así:
bool isValid(char* s);
estos corchetes deben cerrarse en el orden correcto, por ejemplo, "()" y "()[]{}" son todos válidos, pero "(]" , "([)]" y "{{{{" no lo son!

Salí con la siguiente solución de complejidad O (n) time y O (n), que funciona bien:

1. Mantener una pila de personajes.
2. Siempre que encuentre llaves de apertura ''('' , ''{'' O ''['' empújelas en la pila.
3. Siempre que encuentre llaves de cierre '')'' , ''}'' O '']'' , compruebe si la parte superior de la pila corresponde al corchete de apertura, si es así, saque la pila, si no, corte el ciclo y devuelva falso.
4. Repita los pasos 2 - 3 hasta el final de la cadena.

Esto funciona, pero podemos optimizarlo para el espacio, puede ser un espacio extra constante, entiendo que la complejidad del tiempo no puede ser menor que O (n) ya que tenemos que mirar a cada personaje.

Entonces mi pregunta es ¿podemos resolver este problema en O (1) espacio?

Answer 1

Con referencia a la excelente respuesta de Matthieu M. , aquí hay una implementación en C # que parece funcionar muy bien.

/// <summary>
/// Checks to see if brackets are well formed.
/// Passes "Valid parentheses" challenge on www.codeeval.com,
/// which is a programming challenge site much like www.projecteuler.net.
/// </summary>
/// <param name="input">Input string, consisting of nothing but various types of brackets.</param>
/// <returns>True if brackets are well formed, false if not.</returns>
static bool IsWellFormedBrackets(string input)
{
string previous = "";
while (input.Length != previous.Length)
{
previous = input;
input = input
.Replace("()", String.Empty)
.Replace("[]", String.Empty)
.Replace("{}", String.Empty);
}
return (input.Length == 0);
}

Esencialmente, todo lo que hace es eliminar los pares de corchetes hasta que no quede ninguno para eliminar; si queda algo, los paréntesis no están bien formados.

Ejemplos de corchetes bien formados:

()[]
{()[]}

Ejemplo de corchetes malformados:

([)]
{()[}]

Answer 2

Creo que puedes implementar un algoritmo O (n). Simplemente tiene que inicializar una variable de contador para cada tipo: corchetes rizados, cuadrados y normales. Después de lo que debe repetir la cadena y debe aumentar el contador correspondiente si se abre el soporte, de lo contrario, para disminuirlo. Si el contador es negativo, devuelve falso. Después, creo que puede implementar un algoritmo O (n). Simplemente tiene que inicializar una variable de contador para cada tipo: corchetes rizados, cuadrados y normales. Después de lo que debe repetir la cadena y debe aumentar el contador correspondiente si se abre el soporte, de lo contrario, para disminuirlo. Si el contador es negativo, devuelve falso. Después de contar todos los corchetes, debe verificar si todos los contadores son cero. En ese caso, la cadena es válida y debe devolverla como verdadera.

Answer 3

Dudo que encuentres una mejor solución, ya que incluso si usas funciones internas para regularizar o contar las ocurrencias, todavía tienen un costo O (...). Yo diría que tu solución es la mejor :)

Para optimizar el espacio, podría hacer una codificación de longitud de ejecución en su pila, pero dudo que le ganaría mucho, excepto en casos como {{{{{{{{{{}}}}}}}}}} .

Answer 4

En lugar de poner llaves en la pila, podría usar dos punteros para verificar los caracteres de la cuerda. un comienzo desde el comienzo de la cadena y el otro desde el final de la cadena. algo como

bool isValid(char* s) {
start = find_first_brace(s);
end = find_last_brace(s);
while (start <= end) {
if (!IsPair(start,end)) return false;
// move the pointer forward until reach a brace
start = find_next_brace(start);
// move the pointer backward until reach a brace
end = find_prev_brace(end);
}
return true;
}

Tenga en cuenta que no se manejan casos de esquina.

Answer 5

En realidad, hay un algoritmo de espacio de registro determinístico debido a Ritchie y Springsteel: http://dx.doi.org/10.1016/S0019-9958(72)90205-7 ( paywalled, lo siento no en línea). Dado que necesitamos bits de registro para indexar la cadena, esto es óptimo para el espacio.

Si está dispuesto a aceptar un error unilateral, existe un algoritmo que utiliza el espacio n polylog (n) time y polylog (n): http://www.eccc.uni-trier.de/report/2009/119/

Answer 6

Esta es mi solución al problema. O (n) es la complejidad del tiempo sin complejidad del espacio. Código en C.

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
bool checkBraket(char *s)
{
int curly = 0, rounded = 0, squre = 0;
int i = 0;
char ch = s[0];
while (ch != ''/0'')
{
if (ch == ''{'') curly++;
if (ch == ''}'') {
if (curly == 0) {
return false;
} else {
curly--; }
}
if (ch == ''['') squre++;
if (ch == '']'') {
if (squre == 0) {
return false;
} else {
squre--;
}
}
if (ch == ''('') rounded++;
if (ch == '')'') {
if (rounded == 0) {
return false;
} else {
rounded--;
}
}
i++;
ch = s[i];
}
if (curly == 0 && rounded == 0 && squre == 0){
return true;
}
else {
return false;
}
}
void main()
{
char mystring[] = "{{{{{[(())}}]}}}";
int answer = checkBraket(mystring);
printf("my answer is %d/n", answer);
return;
}

Answer 7

Este es un código Java en el que elimino los corchetes de la expresión de la cadena y luego verifico la formación del pozo reemplazando las llaves bien formadas por nulos

input = (a+{b+c}-[de])+[f]-[g] muestra input = (a+{b+c}-[de])+[f]-[g] FilterBrackets dará salida = ({}[])[][] Luego compruebo la buena calidad.

Comentarios bienvenidos.

public class ParanString {
public static void main(String[] args) {
String s = FilterBrackets("(a+{b+c}-[d-e])[][]");
while ((s.length()!=0) && (s.contains("[]")||s.contains("()")||s.contains("{}")))
{
//System.out.println(s.length());
//System.out.println(s);
s = s.replace("[]", "");
s = s.replace("()", "");
s = s.replace("{}", "");
}
if(s.length()==0)
{
System.out.println("Well Formed");
}
else
{
System.out.println("Not Well Formed");
}
}
public static String FilterBrackets(String str)
{
int len=str.length();
char arr[] = str.toCharArray();
String filter = "";
for (int i = 0; i < len; i++)
{
if ((arr[i]==''('') || (arr[i]=='')'') || (arr[i]==''['') || (arr[i]=='']'') || (arr[i]==''{'') || (arr[i]==''}''))
{
filter=filter+arr[i];
}
}
return filter;
}
}

Answer 8

La siguiente modificación de la Sbusidan de Sbusidan es O ( n ² ) complejo de tiempo pero O (log n ) espacio simple.

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
char opposite(char bracket) {
switch(bracket) {
case ''['':
return '']'';
case ''('':
return '')'';
}
}
bool is_balanced(int length, char *s) {
int depth, target_depth, index;
char target_bracket;
if(length % 2 != 0) {
return false;
}
for(target_depth = length/2; target_depth > 0; target_depth--) {
depth=0;
for(index = 0; index < length; index++) {
switch(s[index]) {
case ''('':
case ''['':
depth++;
if(depth == target_depth) target_bracket = opposite(s[index]);
break;
case '')'':
case '']'':
if(depth == 0) return false;
if(depth == target_depth && s[index] != target_bracket) return false;
depth--;
break;
}
}
}
}
void main(char* argv[]) {
char input[] = "([)[(])]";
char *balanced = is_balanced(strlen(input), input) ? "balanced" : "imbalanced";
printf("%s is %s./n", input, balanced);
}

Answer 9

Podría proporcionar el valor y verificar si es válido, imprimiría SÍ, de lo contrario, imprimiría NO

static void Main(string[] args)
{
string value = "(((([{[(}]}]))))";
List<string> jj = new List<string>();
if (!(value.Length % 2 == 0))
{
Console.WriteLine("NO");
}
else
{
bool isValid = true;
List<string> items = new List<string>();
for (int i = 0; i < value.Length; i++)
{
string item = value.Substring(i, 1);
if (item == "(" || item == "{" || item == "[")
{
items.Add(item);
}
else
{
string openItem = items[items.Count - 1];
if (((item == ")" && openItem == "(")) || (item == "}" && openItem == "{") || (item == "]" && openItem == "["))
{
items.RemoveAt(items.Count - 1);
}
else
{
isValid = false;
break;
}
}
}
if (isValid)
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("NO");
}
}
Console.ReadKey();
}

Answer 10

Sé que llegué un poco tarde a esta fiesta; también es mi primera publicación en .

Pero cuando revisé las respuestas, pensé que podría encontrar una mejor solución.

Entonces mi solución es usar algunos consejos.
Ni siquiera tiene que usar ningún almacenamiento RAM, ya que los registros se pueden usar para esto.
No he probado el código; está escrito sobre la marcha.
Necesitarás corregir mis errores tipográficos y depurarlo, pero creo que tendrás la idea.

Uso de memoria: solo la CPU se registra en la mayoría de los casos.
Uso de la CPU: depende, pero aproximadamente el doble del tiempo que lleva leer la cadena.
Modifica la memoria: No.

b: string b eginning, e: string e nd.
Posición l: l , posición derecha.
c: c har, m: m atch char

si r llega al final de la cadena, tenemos éxito.
Voy hacia atrás desde r hacia b.
Siempre que r se encuentre con un nuevo tipo de inicio, establezca l = r.
cuando llego a b, terminamos con el bloque; saltar al comienzo del siguiente bloque.

const char *chk(const char *b, int len) /* option 2: remove int len */
{
char c, m;
const char *l, *r;
e = &b[len]; /* option 2: remove. */
l = b;
r = b;
while(r < e) /* option 2: change to while(1) */
{
c = *r++;
/* option 2: if(0 == c) break; */
if(''('' == c || ''{'' == c || ''['' == c)
{
l = r;
}
else if('')'' == c || '']'' == c || ''}'' == c)
{
/* find ''previous'' starting brace */
m = 0;
while(l > b && ''('' != m && ''['' != m && ''{'' != m)
{
m = *--l;
}
/* now check if we have the correct one: */
if(((m & 1) + 1 + m) != c) /* cryptic: convert starting kind to ending kind and match with c */
{
return(r - 1); /* point to error */
}
if(l <= b) /* did we reach the beginning of this block ? */
{
b = r; /* set new beginning to ''head'' */
l = b; /* obsolete: make left is in range. */
}
}
}
m = 0;
while(l > b && ''('' != m && ''['' != m && ''{'' != m)
{
m = *--l;
}
return(m ? l : NULL); /* NULL-pointer for OK */
}

Después de pensar en este enfoque por un tiempo, me di cuenta de que no funcionará como está ahora.
El problema será que si tiene "[() ()]", fallará cuando llegue al '']''.
Pero en lugar de eliminar la solución propuesta, la dejo aquí, ya que en realidad no es imposible hacerlo funcionar, pero sí requiere algunas modificaciones.

Answer 11

Si la entrada es de solo lectura, no creo que podamos hacer O (1) espacio. Es un hecho bien conocido que cualquier lenguaje decidable de O (1) es regular (es decir, escribible como una expresión regular). El conjunto de cadenas que tiene no es un idioma normal.

Por supuesto, esto es sobre una máquina de Turing. Yo esperaría que sea cierto también para las máquinas de RAM de palabra fija.

Answer 12

Si puede sobreescribir la cadena de entrada (no es razonable en los casos de uso que visualizo, pero qué diablos ...) puede hacerlo en un espacio constante, aunque creo que el requisito de tiempo va hasta O (n ² ) .

Me gusta esto:

string s = input
char c = null
int i=0
do
if s[i] isAOpenChar()
c = s[i]
else if
c = isACloseChar()
if closeMatchesOpen(s[i],c)
erase s[i]
while s[--i] != c ;
erase s[i]
c == null
i = 0; // Not optimal! It would be better to back up until you find an opening character
else
return fail
end if
while (s[++i] != EOS)
if c==null
return pass
else
return fail

La esencia de esto es usar la parte inicial de la entrada como pila.

Answer 13

http://www.sureinterview.com/shwqst/112007

Es natural resolver este problema con una pila.

Si solo se usan ''('' y '')'', la pila no es necesaria. Solo necesitamos mantener un contador para la izquierda no igualada ''(''. La expresión es válida si el contador siempre es no negativo durante la partida y es cero al final.

En general, aunque la pila sigue siendo necesaria, la profundidad de la pila se puede reducir utilizando un contador para llaves sin par.

Answer 14

Editar: Aunque simple, este algoritmo es en realidad O (n ^ 2) en términos de comparaciones de caracteres. Para demostrarlo, uno simplemente puede generar una cadena como ''('' * n + '')'' * n .

Tengo una idea simple, aunque quizás errónea, de que me someteré a sus críticas.

Es un algoritmo destructivo, lo que significa que si alguna vez necesitas la cuerda, no ayudaría (ya que necesitarías copiarla).

De lo contrario, el algoritmo funciona con un índice simple dentro de la cadena actual.

La idea es eliminar pares uno después de los otros:

1. ([{}()])
2. ([()])
3. ([])
4. ()
5. empty -> OK

Se basa en el simple hecho de que si tenemos pares coincidentes, entonces al menos uno es de la forma () sin ningún carácter de par en el medio.

Algoritmo:

1. i := 0
2. Encuentre un par coincidente de i . Si no se encuentra ninguno, la cadena no es válida. Si se encuentra uno, permítame ser el índice del primer personaje.
3. Quite [i:i+1] de la cadena
4. Si estoy al final de la cadena y la cadena no está vacía, es un error.
5. Si [i-1:i] es un par coincidente, i := i-1 y de vuelta a 3.
6. De lo contrario, volvamos a 1.

El algoritmo es O(n) en complejidad porque:

• cada iteración del ciclo elimina 2 caracteres de la cadena
• el paso 2., que es lineal, está naturalmente ligado (no puedo crecer indefinidamente)

Y es O(1) en el espacio porque solo se requiere el índice.

Por supuesto, si no puedes permitirte destruir la cuerda, entonces tendrás que copiarla, y eso es O(n) en el espacio, ¡así que no hay ningún beneficio real allí!

A menos que, por supuesto, estoy profundamente equivocado en alguna parte ... y tal vez alguien podría usar la idea original (hay un par en alguna parte) para tener un mejor efecto.

Answer 15

Usando la programación de c # OOPS ... Solución pequeña y simple

Console.WriteLine("Enter the string");
string str = Console.ReadLine();
int length = str.Length;
if (length % 2 == 0)
{
while (length > 0 && str.Length > 0)
{
for (int i = 0; i < str.Length; i++)
{
if (i + 1 < str.Length)
{
switch (str[i])
{
case ''{'':
if (str[i + 1] == ''}'')
str = str.Remove(i, 2);
break;
case ''('':
if (str[i + 1] == '')'')
str = str.Remove(i, 2);
break;
case ''['':
if (str[i + 1] == '']'')
str = str.Remove(i, 2);
break;
}
}
}
length--;
}
if(str.Length > 0)
Console.WriteLine("Invalid input");
else
Console.WriteLine("Valid input");
}
else
Console.WriteLine("Invalid input");
Console.ReadKey();

Answer 16

var verify = function(text)
{
var symbolsArray = [''[]'', ''()'', ''<>''];
var symbolReg = function(n)
{
var reg = [];
for (var i = 0; i < symbolsArray.length; i++) {
reg.push(''//' + symbolsArray[i][n]);
}
return new RegExp(''('' + reg.join(''|'') + '')'',''g'');
};
// openReg matches ''('', ''['' and ''<'' and return true or false
var openReg = symbolReg(0);
// closeReg matches '')'', '']'' and ''>'' and return true or false
var closeReg = symbolReg(1);
// nestTest matches openSymbol+anyChar+closeSymbol
// and returns an obj with the match str and it''s start index
var nestTest = function(symbols, text)
{
var open = symbols[0]
, close = symbols[1]
, reg = new RegExp(''(//' + open + '')([//s//S])*(//' + close + '')'',''g'')
, test = reg.exec(text);
if (test) return {
start: test.index,
str: test[0]
};
else return false;
};
var recursiveCheck = function(text)
{
var i, nestTests = [], test, symbols;
// nestTest with each symbol
for (i = 0; i < symbolsArray.length; i++)
{
symbols = symbolsArray[i];
test = nestTest(symbols, text);
if (test) nestTests.push(test);
}
// sort tests by start index
nestTests.sort(function(a, b)
{
return a.start - b.start;
});
if (nestTests.length)
{
// build nest data: calculate match end index
for (i = 0; i < nestTests.length; i++)
{
test = nestTests[i];
var end = test.start + ( (test.str) ? test.str.length : 0 );
nestTests[i].end = end;
var last = (nestTests[i + 1]) ? nestTests[i + 1].index : text.length;
nestTests[i].pos = text.substring(end, last);
}
for (i = 0; i < nestTests.length; i++)
{
test = nestTests[i];
// recursive checks what''s after the nest
if (test.pos.length && !recursiveCheck(test.pos)) return false;
// recursive checks what''s in the nest
if (test.str.length) {
test.str = test.str.substring(1, test.str.length - 1);
return recursiveCheck(test.str);
} else return true;
}
} else {
// if no nests then check for orphan symbols
var closeTest = closeReg.test(text);
var openTest = openReg.test(text);
return !(closeTest || openTest);
}
};
return recursiveCheck(text);
};

Answer 17

/**
*
* @author madhusudan
*/
public class Main {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
new Main().validateBraces("()()()()(((((())))))()()()()()()()()");
// TODO code application logic here
}
/**
* @Use this method to validate braces
*/
public void validateBraces(String teststr)
{
StringBuffer teststr1=new StringBuffer(teststr);
int ind=-1;
for(int i=0;i<teststr1.length();)
{
if(teststr1.length()<1)
break;
char ch=teststr1.charAt(0);
if(isClose(ch))
break;
else if(isOpen(ch))
{
ind=teststr1.indexOf(")", i);
if(ind==-1)
break;
teststr1=teststr1.deleteCharAt(ind).deleteCharAt(i);
}
else if(isClose(ch))
{
teststr1=deleteOpenBraces(teststr1,0,i);
}
}
if(teststr1.length()>0)
{
System.out.println("Invalid");
}else
{
System.out.println("Valid");
}
}
public boolean isOpen(char ch)
{
if("(".equals(Character.toString(ch)))
{
return true;
}else
return false;
}
public boolean isClose(char ch)
{
if(")".equals(Character.toString(ch)))
{
return true;
}else
return false;
}
public StringBuffer deleteOpenBraces(StringBuffer str,int start,int end)
{
char ar[]=str.toString().toCharArray();
for(int i=start;i<end;i++)
{
if("(".equals(ar[i]))
str=str.deleteCharAt(i).deleteCharAt(end);
break;
}
return str;
}
}