Pyth es un lenguaje de golf basado en Python. Utiliza la notación de prefijo, y cada comando tiene una aridad diferente (número de argumentos que acepta).
Su tarea es escribir un verificador de sintaxis para un lenguaje similar a Pyth (inexistente), Pith.
Sintaxis de médula
Pith solo tiene 8 comandos de un solo carácter:
01234()"
01234
cada uno tiene una aridad del número correspondiente y, por lo tanto, esperan muchos argumentos después. Por ejemplo,
400010
es un programa Pith correcto porque 4
está seguido por cuatro argumentos 0
0
0
y 10
, el último de los cuales es 1
seguido por el argumento único 0
. Para visualizar esto, podemos mirar el siguiente árbol:
R
|
4
|
-------------
| | | |
0 0 0 1
|
0
donde R
está el nodo raíz Una forma alternativa de pensar sobre esto es que cada número se refiere al número de hijos que tiene el nodo correspondiente en el árbol de arriba.
Aquí hay otro programa Pith válido, con más de un comando base:
210010
correspondiente a
R
|
-------------
| |
2 1
| |
--------- 0
| |
1 0
|
0
Por otra parte,
3120102100
no es un programa Pith correcto porque la inicial 3
solo tiene dos argumentos, que podemos ver mirando el árbol a continuación:
R
|
3
|
------------------------ ??
| |
1 2
| |
2 ------
| | |
------ 1 0
| | |
0 1 0
|
0
Luego (
comienza un sin límite y )
termina un sin límite. Un ilimitado toma cualquier número de argumentos (con avidez) y cuenta como un solo argumento para cualquier comando principal. Todos los ilimitados que todavía estén abiertos al final del programa se cerrarán automáticamente. Un )
comando no es un error si no hay límites ilimitados abiertos, simplemente no hace nada. *
Por ejemplo, el programa Pith
)31(0)0(201000100
corresponde al árbol
R
|
3
|
------------------------------
| | |
1 0 (
| |
( -----------------------------
| | | | | |
0 2 0 0 1 0
| |
------- 0
| |
0 1
|
0
Los ilimitados vacíos están bien, también lo ()
es un programa Pith válido.
Un programa Pith inválido con un sin límite es
12(010
ya que el 2
único recibe un argumento (el ilimitado).
Finalmente, "
comienza y termina una cadena, que siempre es 0 aridad y cuenta como un solo argumento, por ejemplo
2"010""44)()4"
que es solo un 2
ser pasado dos argumentos de cadena "010"
y "44)()4"
. Al igual que los sin límites, las cadenas también pueden estar vacías, y cualquier cadena no cerrada al final del programa se cierra automáticamente.
* Esta parte es diferente del Pyth original, que en realidad hace algo en un caso como 1)
terminar la aridad 1 y generar un error.
De entrada y salida
La entrada será una sola cadena no vacía que consta de solo los caracteres 01234()"
. Opcionalmente, puede suponer que siempre hay una nueva línea final adicional. Puede escribir una función o un programa completo para este desafío.
Debe generar un valor verdadero si la entrada es Pith sintácticamente válida, o un valor falso de lo contrario. Los valores verdadero y falso deben ser fijos, por lo que no puede generar 1
un programa válido y2
otro.
Tanteo
Este es el código de golf, por lo que gana el código en la menor cantidad de bytes.
Casos de prueba
Verdad:
0
)
(
"
()
""
10
400010
210010
("")00
3"""""
(0)))0)1)0
2(2(2(0)0)0)0
2"010""44)()4"
)31(0)0(201000100
())2)1))0"3())"))
3("4321("301(0)21100"4")"123"00)40"121"31000""01010
Falsy
1
1(310
(1)0)
12(010
4"00010"
3120102100
20(2((0)(0)))
2(2(2(0)0)0)01)
4(0102)00)00000
2"00"("00"2(""))
fuente
[( [2 [0] [1 [0] ] ] [0] [1 [0]] [0] ]
? El que tienes tiene ramas de 2, 0, 0, 1 y 0; el segundo no debería estar allí.())2)1))0"3())"))
(que debería ser cierto, creo).()210""
con muchas operaciones noRespuestas:
CJam, 65 bytes
Gosh, desearía que CJam tuviera Regex, esto podría haberse completado en menos de 50 bytes
La idea principal es mantener la reducción de cosas para
0
decir10
que0
,200
a0
y así sucesivamente. Una vez hecho esto, reducimos todos los soportes adaptados a0
, es decir,()
a0
,(0)
a0
,(00)
a0
, y así sucesivamente. Luego repetimos losL
tiempos de ciclo , dondeL
es la longitud de entrada.La cadena de entrada inicialmente pasa por un procesamiento adicional donde ajustamos para que no coincida
"
y agreguemos muchos)
para compensar para que no coincida(
Esto asegura que después de todas las iteraciones, solo deberíamos tener
0
(y no-op)
) en la cadena.Actualización: se corrigió un error por el cual
)
las operaciones sin nivel superior se consideran dañinasExpansión de código
Pruébelo en línea aquí o ejecute toda la suite
fuente
Regex, sabor PCRE, 83 bytes
Pruébalo aquí.
Regex, sabor PCRE, 85 bytes
Pruébalo aquí.
Usé algunas ideas en la respuesta de este dan1111 .
Algunas explicaciones sobre
(?2)*(()(?1))?
.fuente
(?2)*(()(?1))?
es la pieza final del rompecabezas que estaba buscando. Buen hallazgo! ;)(?2)*(()(?1))?
parte correctamente, la(()(?1))?
parte nunca coincide con nada, ya que(?2)*
ya se come todo lo que(()(?1))?
puede coincidir, y esta construcción se usa para establecer el grupo de captura 3 cuando ingresamos(
y desarmar el grupo de captura 3 cuando estamos fuera de la()
construcción (para permitir la coincidencia sin emparejar)
).lex, 182 bytes (157 con pila de tamaño fijo)
Estos programas requieren que la entrada sea una única cadena terminada de nueva línea de caracteres válidos.
El programa anterior se segfault si se queda sin memoria, lo que en teoría podría suceder si le das suficiente
(
. Pero dado que una falla predeterminada cuenta como falla, lo estoy tomando como "falsey", aunque la descripción del problema no dice qué hacer si los recursos no son suficientes.Lo reduje 157 bytes simplemente usando una pila de tamaño fijo, pero eso parecía una trampa.
Compilar:
Prueba:
Prueba de salida:
fuente
80386 Ensamblador, 97 bytes
Volcado hexadecimal:
Esto se ejecuta a través de la entrada una vez, empujando números mayores que cero en la pila y decrementándolos cuando se procesa un cero. Los ilimitados se procesan como -1.
Prototipo de función (en C) (la función devuelve 0 si no es válido y 1 si es válido):
Ensamblaje equivalente (NASM):
El siguiente código en C se puede usar con GCC en un sistema POSIX para probar:
fuente
Python 2, 353 bytes
La función de análisis recorre los tokens de uno en uno y crea un árbol de la estructura del programa. Los programas no válidos desencadenan una excepción que hace que se imprima un cero (Falsy), de lo contrario, el análisis exitoso da como resultado uno.
La salida de las pruebas que muestran la salida del analizador:
El código antes del minificador:
fuente
==
en las pruebas; poner las cadenas primero significa que puede hacerloif')'==q
. Creo que una de lasbreak
declaraciones podría reemplazarsef=0
, ya que eso también lo sacará delwhile f
círculo. Finalmente, en lugar deassert x==y
que pueda usar1/(x==y)
para aZeroDivisionError
. ;)Pip ,
8872 bytesIdea tomada de Optimizer's CJam . Mi puñalada original sobre el problema con un analizador de descenso recursivo fue ... bastante más larga.
Formateado, con explicación:
Trucos interesantes:
0X,5
, por ejemplo, es0 X [0 1 2 3 4] == ["" "0" "00" "000" "0000"]
.R
operador ternario eplace puede tomar una lista de cualquiera de sus argumentos:"abracadabra" R ["br" "ca"] 'b
daababdaba
, por ejemplo. Hago un buen uso de esta función conz
aquí.""
vacía[]
, la lista vacía y cualquier escalar que sea cero. Por lo tanto,0
es falso, pero también0.0
y"0000000"
. Esta característica es inconveniente a veces (para probar si una cadena está vacía, uno debe probar su longitud porque también"0"
es falsa), pero para este problema es perfecta.fuente
Javascript (ES6),
289288285282278244241230 bytesfuente