Escriba un programa que tome una cadena de los cuatro caracteres ()[]
que satisfaga estos puntos:
- Cada paréntesis izquierdo
(
tiene un paréntesis derecho coincidente)
. - Cada soporte izquierdo
[
tiene un soporte derecho a juego]
. - Los pares de paréntesis y corchetes no se superpondrán. por ejemplo,
[(])
no es válido porque los corchetes coincidentes no están completamente contenidos en los paréntesis coincidentes, ni viceversa. - El primer y el último carácter son un par de paréntesis o paréntesis coincidentes. Entonces
([]([]))
y[[]([])]
son válidos pero[]([])
no lo son.
(Una gramática para el formato de entrada es <input> ::= [<input>*] | (<input>*)
).
Cada par de paréntesis y paréntesis coincidentes se evalúa como un entero no negativo:
- Todos los valores de pares dentro de paréntesis coincidentes se suman . La coincidencia vacía
()
tiene valor0
. - Los valores de pares dentro de paréntesis coincidentes se multiplican . La coincidencia vacía
[]
tiene valor1
.
(La suma o producto de un número es ese mismo número).
Por ejemplo, ([](())([][])[()][([[][]][][])([][])])
se puede desglosar y evaluar como 9
:
([](())([][])[()][([[][]][][])([][])]) <input>
(1 (0 )(1 1 )[0 ][([1 1 ]1 1 )(1 1 )]) <handle empty matches>
(1 0 2 0 [(1 1 1 )2 ]) <next level of matches>
(1 0 2 0 [3 2 ]) <and the next>
(1 0 2 0 6 ) <and the next>
9 <final value to output>
Otro ejemplo:
[([][][][][])([][][])([][][])(((((([][]))))))] <input>
[(1 1 1 1 1 )(1 1 1 )(1 1 1 )((((((1 1 ))))))]
[5 3 3 (((((2 )))))]
[5 3 3 ((((2 ))))]
[5 3 3 (((2 )))]
[5 3 3 ((2 ))]
[5 3 3 (2 )]
[5 3 3 2 ]
90 <output>
Su programa necesita evaluar e imprimir el número entero representado por toda la cadena de entrada. Puede asumir que la entrada es válida. El código más corto en bytes gana.
En lugar de un programa, puede escribir una función que tome una cadena e imprima o devuelva el entero.
code-golf
arithmetic
balanced-string
recursion
Pasatiempos de Calvin
fuente
fuente
Respuestas:
CJam, 23
¡Con GRANDES créditos para Dennis! Pruébalo en línea
Explicación:
El programa convierte la entrada en una expresión CJam y luego la evalúa.
[…]
se convierte[…1]:*
(agrega 1 y multiplica) se(…)
convierte[…0]:+
(agrega 0 y agrega)fuente
q"])(""1]:*0]:+["4/ers~
Lisp común - 98
(
por(+
[
por(*
]
por)
Esto requiere que la
cl-ppcre
biblioteca se cargue en la imagen lisp actual.Explicación
Funciona
*
y+
es variable y devuelve su valor neutral cuando no se le dan argumentos. Para sus ejemplos, la forma de lisp evaluada es la siguiente:y
Sin expresiones regulares: 183 bytes
Vamos, Lisp - 16 bytes (experimental)
Otros idiomas son tan concisos que me siento tentado a hacer mi propio lenguaje de golf basado en Common Lisp, para manipulaciones de cuerdas más cortas. Actualmente no hay especificación, y la función eval es la siguiente:
Pruebas:
s
y dos pilas,p
yq
.p
.<
: aparecep
y empuja haciaq
.r
: reemplazas
(debe ser una cadena) de caracteres enq
caracteresp
; el resultado se almacena ens
;p
yq
se vacíanR
: lee de la cadenas
, almacena el resultado en una variables
.E
: evalúe la formas
, almacene el resultado ens
.fuente
Pyth,
353433 bytesDemostración.
1 byte gracias a @Jakube.
Comenzamos analizando la entrada. El formato de entrada está cerca de Python, pero no del todo. Necesitamos comas después de cada grupo entre paréntesis o entre corchetes. La coma al final de un grupo entre corchetes es innecesaria, pero inofensiva. Para lograr esto, usamos este código:
Esto dejará un extra
,
al final de la cadena, que envolverá todo el objeto en una tupla, pero esto es inofensivo, porque la tupla se sumará y tendrá un valor igual a su elemento.Ahora que la cadena se analiza, debemos encontrar su valor. Esto se realiza mediante una función definida por el usuario
y
, que se llama en el objeto analizado. la función se define de la siguiente manera:fuente
Emacs lisp, 94
El formato se ve muy lispy, así que pensé que una transformación simple podría funcionar:
El formato intermedio se parece a (para el ejemplo en la pregunta):
Nos ayuda el hecho de que la suma y la multiplicación ya hacen lo que queremos con una lista de argumentos vacía.
Degolfed, e interactivo, para que juegues placer:
fuente
interactive
(en lugar de buffer-string, usa read-from-string).Retina , 111 bytes
Da salida en unario.
Cada línea debe ir a su propio archivo, pero puede ejecutar el código como un archivo con la
-s
bandera. P.ej:La explicación viene después.
fuente
Java, 349 caracteres
Un enfoque recursivo simple. Espera que la cadena sea el primer argumento utilizado para llamar al programa.
Expandido:
fuente
Perl 5, 108
Hecho como intérprete en lugar de reescribir y evaluar. No es una gran muestra, pero es divertido escribir de todos modos.
Sin golf:
fuente
Python, 99
Probé una variedad de métodos, pero lo más corto que pude obtener fue básicamente un reemplazo y evaluación. Me sorprendió gratamente descubrir que podía dejar todos los mensajes finales
,
, ya que Python puede analizar[1,2,]
y la coma final final simplemente pone todo en una tupla. La única otra parte no sencilla sería laord(c)%31%7
de separar los diferentes personajes (que se evalúa como2
,3
,1
,0
para(
,)
,[
,]
respectivamente)fuente
Java, 301
un enfoque un poco diferente a la respuesta de TheNumberOne, aunque la mía también es de naturaleza recursiva. La entrada se toma de la línea de comando. El método nulo guarda algunos bytes al eliminar los caracteres que ya no son necesarios.
expandido:
fuente
Python,
117110109 bytesUn aspecto con el que estaba luchando es que la función básicamente tiene dos valores de retorno: el producto / suma y la nueva posición en la cadena. Pero necesito una función que solo devuelva el resultado, por lo que devolver una tupla no funciona. Esta versión usa un argumento de "referencia" (lista con un elemento), para pasar la posición de regreso de la función.
Tengo una versión más corta (103 bytes) que usa una variable global para la posición. Pero eso solo funcionará en la primera llamada. Y una función que solo funciona una vez parece un poco sospechosa. No estoy seguro de si sería aceptable para el código de golf.
El algoritmo es la recursividad directa. Intenté varias variaciones para la expresión que actualiza el producto / suma. Se me ocurrieron algunas versiones que tenían exactamente la misma longitud, pero ninguna más corta.
Esperaba que el enfoque que convierte esto en una expresión que se evalúa probablemente gane. Pero como dicen: "iterar es humano, recurrir a lo divino".
fuente
Clojure - 66 bytes
Tenga en cuenta que
([] (()) ([] []) [()] [([[] []] [] []) ([] [])])
es un formulario válido de Clojure. Entonces:g
.g
función local se aplica+
o*
al resultado de la invocación deg
en sub-elementos de sus argumentos.x
en una secuencia vacía;(map g x)
devuelvenil
yapply
devuelve el valor neutral para la operación.fuente
JavaScript (ES6), 116 bytes
fuente