Debe escribir un programa o función que tome una cadena de corchetes y genere si esa cadena coincide o no completamente. Su programa debe imprimir un valor verdadero o falso , y IO puede estar en cualquier formato razonable .
Reglas y definiciones:
A los efectos de este reto, un "soporte" es cualquiera de los siguientes caracteres:
()[]{}<>
.Un par de paréntesis se considera "coincidente" si los paréntesis de apertura y cierre están en el orden correcto y no tienen caracteres dentro de ellos, como
() []{}
O si cada subelemento dentro de él también coincide.
[()()()()] {<[]>} (()())
Los subelementos también se pueden anidar en varias capas de profundidad.
[(){<><>[()]}<>()] <[{((()))}]>
Una cadena se considera "Totalmente coincidente" si y solo si:
Cada personaje es un paréntesis,
Cada par de soportes tiene el soporte de apertura y cierre correcto y en el orden correcto, y
Cada soporte se corresponde.
Puede suponer que la entrada solo contendrá ASCII imprimible .
Prueba IO
Aquí hay algunas entradas que deberían devolver un valor verdadero:
()
[](){}<>
(((())))
({[<>]})
[{()<>()}[]]
[([]{})<{[()<()>]}()>{}]
Y aquí hay algunas salidas que deberían devolver un valor falso:
( Has no closing ')'
}{ Wrong order
(<)> Each pair contains only half of a matched element
(()()foobar) Contains invalid characters
[({}<>)> The last bracket should be ']' instead of '>'
(((())) Has 4 opening brackets, but only 3 closing brackets.
Como de costumbre, este es el código de golf, por lo que se aplican las lagunas estándar y gana la respuesta más corta en bytes.
fuente
[}
un partido? Y si no, ¿dónde está excluido por estas reglas?Each pair of brackets has the correct opening and closing bracket and in the right order.
Respuestas:
05AB1E , 19 bytes
La entrada se da entre comillas . Código:
Bueno, mierda, se encontraron muchos errores y características no implementadas. Explicación:
Esta es en realidad una parte difícil. Lo que se ve en pseudocódigo es:
Esto está cubierto por esta parte del código 05AB1E :
Como puede ver, este es un reemplazo infinito (hecho hasta que la cadena ya no cambie). Por lo tanto, no tengo que preocuparme por configurar el reemplazo en un bucle, ya que esto ya está incorporado. Después de esto:
Utiliza la codificación CP-1252 . Pruébalo en línea! (ligeramente modificado porque la versión anterior está en desuso).
fuente
õ
se agregara?Brain-Flak ,
1101, 1085, 981 bytesPruébalo en línea!
Esto es 980 bytes de código fuente, y
+1
para el-a
indicador que permite la entrada ASCII (pero la salida decimal)Esta es una respuesta que he querido escribir durante mucho, mucho tiempo. Al menos 6 meses. Esperé para publicar esto porque sabía que responder a este desafío sería muy difícil en ataques cerebrales. Pero vale la pena por una razón muy importante: el código fuente en sí mismo es una entrada verdadera, que es el punto central de este lenguaje.
Y mientras escribía sobre esto , esta pregunta fue lo que me inspiró a escribir cerebro-flak.
Esta respuesta tardó aproximadamente dos horas en escribirse. Admito que está bastante mal, sobre todo porque se repite gran parte del código para cada tipo de soporte. Pero estoy asombrado de haber podido escribir una respuesta, especialmente dado que Brain-Flak es
Voy a intentar jugar golf más tarde, pero quería sacar esto de todos modos.
Tengo una explicación detallada, pero tiene aproximadamente 6 mil caracteres, así que creo que no sería prudente pegar todo en esta respuesta. Puedes leerlo aquí si quieres. Agregaré una explicación más corta aquí.
La idea básica es que repetimos los siguientes pasos para cada personaje en la pila:
Verificamos cada personaje para ver si coincide con algún paréntesis. Si se trata de un paréntesis de apertura, insertamos un número en la otra pila de acuerdo con la siguiente asignación:
Luego verificamos si coincide con algún soporte de cierre. Si lo hace, empujamos el número equivalente en la pila alternativa, al igual que para abrir paréntesis. Luego , verificamos si los dos números superiores son iguales. Si lo son, los dos aparecen y el programa continúa de manera normal. Si no lo están, limpiamos ambas pilas (para detener el bucle) y empujamos una en la pila alternativa. Esto es esencialmente una declaración de "ruptura".
Después de verificar los 8 tipos de paréntesis, empujamos el valor de esta ejecución a través del ciclo. Como ponemos a cero la mayor parte, los únicos fragmentos que tienen algún valor son los condicionales cuando los comparamos con los corchetes. Entonces, si cualquier paréntesis coincide, el ciclo completo tiene un valor de 1. Si ninguno de ellos lo hizo, el ciclo completo tiene un valor de 0. En este caso, borraremos ambas pilas y colocaremos un 0 en la pila alternativa. Nuevamente, esto es como una declaración de "descanso".
Después de que se ejecuta este bucle principal, el resto es bastante simple. Estamos en la pila principal (vacía), y la pila alternativa está vacía (si los paréntesis coincidieron) o no vacía si no lo estaban. Entonces ejecutamos esto:
Esto empujará un 0 o un 1 a la pila principal, y cuando el programa finalice, se imprimirá implícitamente.
Gracias a @WheatWizard por crear un buen fragmento "igual" y "lógico no" de limpieza de pila, y por actualizar regularmente el wiki de github con ejemplos útiles.
Gracias a @ ASCII-only por escribir un metagolfer entero en línea que ayudó enormemente a escribir este programa
revisiones
Se eliminó algo de redundancia push pop
Cambié mi lógica de contador cero
fuente
Cerebro-Flak ,
204196190 bytesPruébalo en línea!
-8 bytes gracias al asistente de trigo. -6 bytes gracias a Jo King.
Explicación
Este programa almacena los códigos de caracteres de todos los corchetes no cerrados actuales en la segunda pila. Los pares de soportes
<>
,[]
y{}
cada uno tiene los códigos de caracteres que difieren en exactamente 2, así que no hay necesidad de comprobar específicamente para ellos. El par()
solo difiere en 1, por lo que verificamos(
específicamente y disminuimos efectivamente ese byte (en realidad incrementamos cada dos bytes) antes de continuar.fuente
([{}]<>({}))((){[()](<{}>)}{})
({<>[()]}())
-6 bytesJavaScript (ES6),
5250 bytesQuite los corchetes repetidamente hasta que el resultado sea el mismo que el original, luego devuelva falso a menos que la cadena esté ahora vacía.
Editar: Guardado 2 bytes gracias a @ edc65.
fuente
Retina, 20 bytes
Pruébalo en línea
fuente
CJam,
25242321 bytesGracias a Sp3000 por guardar 2 bytes.
Gracias a jimmy23013 por guardar 2 bytes.
Banco de pruebas.
Trabaja esencialmente el mismo que el otro responde: nos quitamos repetidamente
()
,[]
,<>
y{}
de la cadena y comprobar si terminamos con la cadena vacía. Para evitar tener que verificar cuando hayamos terminado, eliminamos los pares deN
veces dondeN
está la longitud de la cadena, que siempre es suficiente (ya que cada iteración eliminará al menos dos caracteres, a menos que hayamos terminado). Me alegra ver que esto no supera a Retina. :) (Aunque Pyth o Jelly podrían ...)Aquí hay un truco divertido de golf: para obtener la cuerda
()<>[]{}
usamos lo siguiente:El,
{()<>}
es solo un bloque (es decir, una función), que contiene los otros corchetes como código. Cona
envolvemos el bloque en una matriz. El`
stringifica esa matriz, que da"[{()<>}]"
. Finalmente, clasificamos la cadena con$
, que reorganiza los corchetes()<>[]{}
.fuente
()<>[]{}`
que funcionaría igual de bien y tendría la misma cantidad de bytes, ¿verdad?()<>
hay cuatro operadores (decremento, incremento y luego comparación o truncamiento según los operandos), que se ejecutarían de inmediato, mientras que{}
denota un bloque (el equivalente de CJam de una función), es decir, un fragmento de código que se acaba de insertar en la pila sin evaluarlo de inmediato. Es por eso que necesito{}
ajustar el()
y<>
, pero luego usarloa
para poner todo en una matriz es más corto que[...]
.Python, 67 bytes
Genera y evalúa una expresión que se parece a
y comprueba si el resultado está vacío.
Sp3000 ahorró 8 bytes al señalar que
[],(),{}
se pueden subtitular sin comillas porque son objetos de Python y que dos parens no eran necesarios.fuente
Yacc, 119 bytes
No utiliza regex / replace.
Sin golf
Compilacion
Uso
fuente
Pyth,
312524 bytesGolfed hasta 25 bytes gracias a FryAmTheEggMan Eliminado 1 byte
Pruébelo aquí: ¡ conjunto de pruebas !
Todavía soy un novato Pyth, cualquier ayuda es apreciada.
Explicación
Por cierto, felicidades a la otra respuesta Pyth (que actualmente es de 20 bytes)
fuente
Vz=:z"<>|\[]|{}|\(\)"k;!z
. Particularmente notable, básicamente nunca necesita usarlol
si realmente no necesita el número, y=
adivina automáticamente la primera variable utilizada en una expresión. Avíseme si desea que le explique algo más en la sala de chat de Pyth :)l
era innecesario, es bueno saberlo. Al principio, declaró una función porque mi lógica era diferente, y olvidé eliminarla. ¿Debo incluir tu respuesta a la mía? (Soy un novato>. <)Pyth, 20 bytes
Pruébelo en línea: Test Suite
Repetidamente elimina las apariciones de
[]
,()
,<>
y{}
por la división y la re-fusión. Comprueba si la cadena resultante está vacía o no.fuente
Javascript ES6, 54 bytes
Utiliza una implementación recursiva de reemplazo. Suficientemente simple.
fuente
Regex (sabor PCRE),
4137 bytesSolo una solución estándar con expresiones regulares recursivas.
Gracias jimmy23013 por reducir 4 bytes
fuente
Perl,
3433 bytesIncluye +2 para
-lp
Ejecutar con entrada en STDIN:
brackets.pl
:Encuentra el primer par de paréntesis sin nada entre ellos y lo elimina siempre que haya alguno. Luego verifica si la cadena final está vacía.
fuente
s/\(\)|\[]|<>|{}//&&redo;$_=!$_
funcionaria? :)Brain-Flak , 204 bytes
Pruébalo en línea!
No es tan corto como la respuesta de Nitroden , pero utiliza un enfoque muy diferente. Éste se ejecuta a través de la entrada repetidamente, eliminando pares de corchetes adyacentes cada vez hasta que no quede ninguno. En ese punto, si queda algo en la pila, entonces la cadena no coincidía completamente.
Explicación:
fuente
Brainfuck, 132 bytes
Formateado:
Espera entrada sin una nueva línea final. Imprime
\x00
para falso y\x01
para verdadero.Pruébalo en línea.
Enfoque: mantenga una pila comenzando
\x01
y presione el corchete de cierre correspondiente cada vez que se encuentre un corchete de apertura. Antes de verificar si el carácter actual es un paréntesis de apertura, primero verifique si es igual al paréntesis de cierre en la parte superior de la pila, y si es así, revíselo. Si no es el corchete de cierre adecuado ni el corchete de apertura, consuma el resto de la entrada mientras mueve el puntero hacia la derecha. Al final, verifique si el puntero está al lado de la inicial\x01
.fuente
Grime v0.1, 34 bytes
Imprime
1
para un partido y0
para ningún partido. Pruébalo en línea!Explicación
Grime es mi lenguaje de coincidencia de patrones 2D diseñado para este desafío ; También se puede utilizar para unir cadenas 1D. Esta es mi primera respuesta con eso. Modifiqué Grime hoy, pero solo para cambiar el carácter de un elemento de sintaxis (en
`
lugar de,
), para que no afecte mi puntaje.fuente
Reng v.3.3, 137 bytes, sin competencia
Pruébalo aquí!
Hay un poco más de golf por hacer, pero al menos funciona. Agregué un comando
ð
para realizar un seguimiento de las pilas después de este desafío para que esto sea remotamente posible / fácil. Explicaré esto un poco, pero generalmente realiza un seguimiento de todas las cadenas iteradas y busca repeticiones; Si hay una repetición, entonces la cadena es irreducible. De lo contrario, la cadena se reducirá a la cadena / pila vacía y se generará1
. De lo contrario, no se producirá ninguna salida.fuente
PowerShell v2 +,
6362 bytesNo se puede detectar JavaScript, pero actualmente está eliminando los otros que no son esolangs.
Enfoque similar como otras respuestas: un bucle simple que continúa tanto tiempo como podemos eliminar uno de
[]
,()
o<>
(con varios caracteres extraños, porque tenemos que escapar de los especiales de expresiones regulares). Usamos$b
como ayudante en el camino para recordar cómo se estableció nuestro bucle anterior$a
. Una variable no inicializada es$null
, por lo tanto, la primera vez que se encuentra el bucle,$a
obviamente no es igual a$null
.Al final del ciclo,
$a
está vacío o no, y el Booleano-no de esa cadena esTrue
oFalse
.Ejemplo
fuente
C,
121122114 bytes¡Afeitado de 8 bytes gracias a @xsot!
Utiliza una pila.
fuente
c%7&2
. En realidad, no necesitask
. En su lugar, simplemente puede incrementar el lugari
donde lo modificaría,k
ya que dei
todos modos debe verificar si es cero. Algo como esto (código no probado):a[99],i;main(c){for(;read(0,&c,1);c%7&2?i+=a[i--]^c/9:(a[++i]=c/9))i+=!strchr("()[]{}<>",c);putchar(48+!i);}
.a[99],i,k;main(c){for(;read(0,&c,!k);c%7&2?k|=a[i--]^c/9:(a[++i]=c/9))k|=!strchr("()[]{}<>",c);putchar(48+!i*!k);}
a[99],i;main(c){for(;read(0,&c,1);c%7&2?i+=a[i]^c/9?1:-1:(a[++i]=c/9))i+=!strchr("()[]{}<>",c);putchar(48+!i);}
Pero esto todavía no funciona para entradas como()))
, ya que el "estallido" de la pila en realidad no pone a cero los valores en la matriz.Java 7,
156151 bytesNo espero que gane ningún premio, pero todavía no vi una respuesta de Java. Además, me gusta acechar alrededor de PPCG y me gustaría poder votar / comentar otras respuestas.
La entrada se proporciona como parámetros del programa. Esto sigue el mismo formato que muchas otras respuestas aquí, ya que forma un reemplazo de expresiones regulares en un bucle. Originalmente lo hice bucle N veces donde N es la longitud de la cadena original pero el bucle
Integer.MAX_VALUE
es más corto:]. Esto debería estar bien porqueInteger.MAX_VALUE
es la longitud máxima de aString
en Java, por lo que hay una suposición implícita de que la longitud de entrada es algo que Java puede manejar. El tiempo de ejecución es bastante malo (tomó alrededor de 20 minutos en mi computadora portátil) a causa del bucle, pero no vi ninguna restricción al respecto.fuente
Haskell , 151 bytes
Pruébalo en línea!
fuente
(#)
debe llamarse con la cadena vacía como segundo argumento, debe contar(#"")
para el recuento de bytes. También soloTrue
yFalse
se consideran verdadero / falso, consulte la Guía de reglas de golf .a:x#b:y|a==b=x#y
, reduciendo los bytes a 113: ¡ Pruébelo en línea!Python 2.7, 96 bytes
fuente
Python 2, 80 bytes
fuente
Julia, 51 bytes
La menos loca de varias opciones. Como era de esperar, aprovechar el poder de la expresión regular es el camino más corto para la coincidencia de cadenas, pero esto realmente solo se aplica si el patrón para coincidir es regular. Intentar hacer patrones recursivos PCRE termina aumentando el tamaño del código, ya sea al ver si la cadena completa es la coincidencia o al anclar los extremos y luego crear una construcción para especificar el cuerpo interno para la recursividad de expresiones regulares. Ninguno de los dos es bonito o propicio para el golf codificado.
Explicación:
La función elimina repetidamente pares de paréntesis adyacentes de su único argumento, y devuelve verdadero si puede derivar una cadena vacía de esta manera.
fuente
sed,
3936 bytes (34 para código, 2 para -r)Pruébalo en línea!
Versión sed de lo que parece ser el enfoque estándar. Requiere expresiones regulares extendidas (
sed -r
)Guardado 3 bytes gracias a Cows quack
fuente
a
es:a
yta
guardar bytesq
de/./
y soltar las llaves allí también. Pruébalo en línea! Esto se debe a cómoc
funciona el05AB1E, 9 bytes
La entrada se da entre comillas.
Pruébalo en línea!
Explicación:
fuente
Clojure, 153 bytes
Más tiempo que incluso C y Brainfuck responden: o
No usa expresiones regulares, en su lugar usa el primer carácter para determinar cuál es la etiqueta de cierre y encuentra el primer índice donde ese corchete está equilibrado (la suma acumulativa es cero). Luego verifica iterativamente que lo que está entre corchetes y después de los corchetes son válidos.
Tengo que ver si hay un mejor enfoque ...
fuente
Lua , 295 bytes
Versión sin golf
Pruébalo en línea!
fuente
Japt v2.0a0
-!
, 16 bytesIntentalo
fuente
R, 298
El enfoque aquí es convertir la secuencia en código R y luego intentar analizarla y evaluarla. Si eso da un error, entonces regrese
FALSE
.Pero hay un pequeño problema ... reglas de R como soportes son diferentes, por lo que
<
y>
no son soportes en absoluto, y los otros tipos tienen sus propias reglas. Esto se resuelve con un enfoque revolucionario: una función chirriante, cuya única función es señalar un error si su cabeza y cola chirrían de diferentes maneras.Por ejemplo,
[]
se transforma enS('[', {}, ']')
, donde S se define como ...Debido a que el chirrido de la cabeza y el de la cola coinciden, no se produce ningún error.
Algunos otros ejemplos (la parte izquierda es una secuencia de paréntesis y la parte derecha es su transformación en un código R válido que se puede evaluar):
Algunas otras secuencias de paréntesis darán lugar a errores de análisis:
Entonces, la parte restante solo detecta los errores y devuelve FALSO si hay alguno, y VERDADERO si no hay ninguno.
El código humano-legible:
Aplicandolo en casos de muestra:
fuente