Pyth é uma linguagem de golfe baseada em Python. Ele usa notação de prefixo, com cada comando tendo uma aridade diferente (número de argumentos que aceita).

Sua tarefa é escrever um verificador de sintaxe para uma linguagem do tipo Pyth (inexistente), Pith.

Sintaxe da medula

O Pith possui apenas 8 comandos de caractere único:

01234()"

01234cada um tem uma aridade do número correspondente e, portanto, espera muitos argumentos depois dele. Por exemplo,

400010

é um programa Pith correto porque 4é seguido por quatro argumentos 0 0 0e 10, o último dos quais é 1seguido pelo argumento único 0. Para visualizar isso, podemos olhar para a seguinte árvore:

      R
      |
      4
      |
-------------
|   |   |   |
0   0   0   1
            |
            0

onde Ré o nó raiz. Uma maneira alternativa de pensar sobre isso é que cada número se refere ao número de filhos que o nó correspondente possui na árvore acima.

Aqui está outro programa Pith válido, com mais de um comando base:

210010

correspondente a

           R
           |
     -------------
     |           |
     2           1
     |           |
 ---------       0
 |       |
 1       0
 |
 0

Por outro lado,

3120102100

não é um programa Pith correto, porque a inicial 3possui apenas dois argumentos, que podemos ver observando a árvore abaixo:

                R
                |
                3
                |
     ------------------------ ??
     |          |
     1          2
     |          |
     2        ------
     |        |    |
   ------     1    0
   |    |     |
   0    1     0
        |
        0

Em seguida, (inicia um ilimitado e )termina um ilimitado. Um ilimitado recebe qualquer número de argumentos (avidamente) e conta como um único argumento para qualquer comando pai. Quaisquer limites ainda abertos até o final do programa são fechados automaticamente. Um )comando não é um erro se não houver limites ilimitados - ele simplesmente não faz nada. *

Por exemplo, o programa Pith

)31(0)0(201000100

corresponde à árvore

            R
            |
            3
            |
    ------------------------------
    |       |                    |
    1       0                    (
    |                            |
    (              -----------------------------
    |              |      |      |      |      |
    0              2      0      0      1      0
                   |                    |
                -------                 0
                |     |
                0     1
                      |
                      0

Os limites ilimitados são ()válidos , assim como um programa Pith válido.

Um programa Pith inválido com um limite é

12(010

já que o 2único recebe um argumento (o ilimitado).

Finalmente, "inicia e termina uma string, que é sempre 0 arity e conta como um único argumento, por exemplo

2"010""44)()4"

que é apenas uma 2passagem de dois argumentos de string "010"e "44)()4". Como sem limites, as seqüências de caracteres também podem estar vazias, e quaisquer seqüências de caracteres não fechadas no final do programa são fechadas automaticamente.

^{* Esta parte é diferente do Pyth original, que realmente faz algo em um caso como 1), encerrando a aridade 1 e gerando um erro.}

Entrada / saída

A entrada será uma única seqüência de caracteres não vazia que consiste apenas nos caracteres 01234()". Opcionalmente, você pode assumir que uma nova linha à direita adicional esteja sempre presente. Você pode escrever uma função ou um programa completo para esse desafio.

Você deve gerar um valor verdadeiro se a entrada for Pith sintaticamente válida ou um valor falso, caso contrário. Os valores de verdade e falsidade devem ser fixos, para que você não possa produzir 1para um programa válido e 2para outro.

Pontuação

Isso é código-golfe, então o código com o menor número de bytes vence.

Casos de teste

Verdade:

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(""))

CJam, 65 bytes

q'"/La+2%{0s*}:Z~_,:L')*+{L{4{)_Z+s/Z}/L{'(\Z')++/Z}/}*')-}2*0s-!

Puxa, eu gostaria que o CJam tivesse Regex, isso poderia ter sido concluído em menos de 50 bytes

A idéia principal é continuar reduzindo as coisas para 0ie 10para 0, 200para 0e assim por diante. Uma vez feito isso, podemos reduzir todas as faixas corresponde a 0, ou seja, ()para 0, (0)para 0, (00)para 0e assim por diante. Repetimos os Ltempos do ciclo , onde Lestá o comprimento da entrada.

A string de entrada inicialmente passa por um processamento extra, onde ajustamos para incomparável "e adicionamos muito )para compensar por incomparável(

Isso garante que, após todas as iterações, devamos ter 0(e não-op )) apenas a string.

Atualização - foi corrigido um erro em que as operações )não operacionais de nível superior são consideradas prejudiciais

Expansão de código

q'"/La+2%{0s*}:Z~_,:L')*      "Part 1 - Preprocessing";
q'"/                          "Read the input and split it on quote";
    La+                       "Add an extra empty array to the split array to compensate";
                              "for unmatched ending quote";
        2%                    "Take every other splitted part, ignoring the contents";
                              "of the strings in the code";
          {0s*}:Z~            "Join the parts by string 0. Also create a function Z";
                              "that does that for future use. We are now done with";
                              "reducing "XYZ" to 0 ";
                  _,:L        "Store the length of the remaining code in L";
                      ')*     "Append L ) to the string to compensate for unmatched (";

{L{4{)_Z+s/Z}/L{'(\Z')++/Z}/}*')-}2*   "Part 2 - the reducing loop";
 L{                         }*         "Run the reduction logic L times";
   4{)_Z+s/Z}/                         "Part 2a - reducing arities";
   4{       }/                         "Run the iteration for 0, 1, 2 and 3";
     )_                                "Increment the iteration number and make a copy";
       Z+s                             "Get that many 0 and append it to the number";
          /Z                           "Split the code onto this number and convert it";
                                       "to 0. This successfully reduces 10, 200, ";
                                       "3000 and 4000 to 0";
              L{'(\Z')++/Z}/           "Part 2b - reducing groups";
              L{          }/           "Run the iteration for 0 through L - 1";
                '(\Z')++               "Get the string '(<iteration number of 0>)'";
                        /Z             "split on it and join by 0. This successfully";
                                       "reduces (), (0), (00) and so on .. to 0";
                              ')-      "After running the part 2 loop L times, all";
                                       "reducible arities and brackets should be reduced";
                                       "except for cases like '30)00' where the no-op )";
                                       "breaks the flow. So we remove ) from the code";
                                       "and run Part 2 L times again";

0s-!                          "Now, if the code was valid, we should only have 0 in the";
                              "remaining code. If not, the code was invalid";

Experimente online aqui ou execute todo o conjunto

Regex, sabor PCRE, 83 bytes

^(?3)*\)*$(()((?(2)|\)*)(\((?1)*(\)|$)|0|"[^"]*.?|(1|(2|(3|4(?3))(?3))(?3))(?3))))?

Experimente aqui.

Regex, sabor PCRE, 85 bytes

^((?(3)|\)*)(?>\((?2)*(()(?1))?(\)|$)|0|"[^"]*.?|(1|(2|(3|4(?1))(?1))(?1))(?1)))*\)*$

Experimente aqui.

Usamos algumas idéias na resposta deste dan1111 .

Algumas explicações sobre(?2)*(()(?1))? .

lex, 182 bytes (157 com pilha de tamanho fixo)

Esses programas requerem que a entrada seja uma única sequência terminada de nova linha de caracteres válidos.

%%
 int n=0,s=0,*t=0;
[0-4] n+=*yytext-48-!!n;
\( (t=realloc(t,(s+1)*sizeof n))[s++]=n-!!n;n=0;
\) if(s&&n)exit(1);s&&(n=t[--s]);
\"[^"]*.? n-=!!n;
\n while(s)t[--s]&&n++;exit(!!n);

O programa acima falhará se ficar sem memória, o que teoricamente poderia acontecer se você o suficiente (. Mas como um segfault conta como falha, eu estou tomando isso como "falsey", embora a descrição do problema não diga o que fazer se os recursos não forem suficientes.

Cortei 157 bytes usando apenas uma pilha de tamanho fixo, mas isso parecia trapaça.

%%
 int n=0,s=0,t[9999];
[0-4] n+=*yytext-48-!!n;
\( t[s++]=n-!!n;n=0;
\) if(s&&n)exit(1);s&&(n=t[--s]);
\"[^"]*.? n-=!!n;
\n while(s)t[--s]&&n++;exit(!!n);

Compilar:

flex -o pith.c pith.l    # pith.l is the above file
c99 -o pith pith.c -lfl

Teste:

while IFS= read -r test; do
  printf %-78s "$test"
  if ./pith <<<"$test"; then echo "OK"; else echo "NO"; fi
done <<EOT
0
)
(
"
()
""
10
400010
210010
("")00
3"""""
2(2(2(0)0)0)0
2"010""44)()4"
)31(0)0(201000100
3("4321("301(0)21100"4")"123"00)40"121"31000""01010
1
1(310
12(010
4"00010"
3120102100
20(2((0)(0)))
2(2(2(0)0)0)01)
4(0102)00)00000
2"00"("00"2(""))
EOT

Saída de teste:

0                                                                             OK
)                                                                             OK
(                                                                             OK
"                                                                             OK
()                                                                            OK
""                                                                            OK
10                                                                            OK
400010                                                                        OK
210010                                                                        OK
("")00                                                                        OK
3"""""                                                                        OK
2(2(2(0)0)0)0                                                                 OK
2"010""44)()4"                                                                OK
)31(0)0(201000100                                                             OK
3("4321("301(0)21100"4")"123"00)40"121"31000""01010                           OK
1                                                                             NO
1(310                                                                         NO
12(010                                                                        NO
4"00010"                                                                      NO
3120102100                                                                    NO
20(2((0)(0)))                                                                 NO
2(2(2(0)0)0)01)                                                               NO
4(0102)00)00000                                                               NO
2"00"("00"2(""))                                                              NO

80386 Montador, 97 bytes

Despejo hexagonal:

0000000: 8b54 2404 5589 e531 c96a ff8a 022c 303c  .T$.U..1.j...,0<
0000010: f275 04f6 d530 c084 ed75 263c f875 0141  .u...0...u&<.u.A
0000020: 3cf9 750f 84c9 7419 4958 3c00 7c03 50eb  <.u...t.IX<.|.P.
0000030: 2430 c084 c075 0958 483c ff7f 0140 ebf3  $0...u.XH<...@..
0000040: 5042 8a02 84c0 75c5 4a84 edb0 2275 be84  PB....u.J..."u..
0000050: c9b0 2975 b85a 31c0 39e5 7501 4089 ec5d  ..)u.Z1.9.u.@..]
0000060: c3                                       .

Isso percorre a entrada uma vez, pressionando números maiores que zero na pilha e diminuindo-os quando um zero é processado. Não consolidadas são processadas como -1.

Protótipo da função (em C) (a função retorna 0 se inválida e 1 se válida):

int __cdecl test(char *in);

Montagem equivalente (NASM):

bits 32
; get input pointer into edx
mov edx, [esp+4]                ; 8B 54 24 04

; save ebp; set ebp = esp
push ebp                        ; 55
mov ebp, esp                    ; 89 E5

; clear ecx
xor ecx, ecx                    ; 31 C9

; push base -1
push byte(-1)                   ; 6A FF

; get top char
mov al, [edx]                   ; 8A 02

    sub al, 0x30                ; 2C 30

    ; if al == quote
    cmp al, 0xF2                ; 3C F2
    jne $+6                     ; 75 04
        ; set ch (in quote?) to opposite
        not ch                  ; F6 D5
        ; set value to 0
        xor al, al              ; 30 C0

    ; if in quote, continue
    test ch, ch                 ; 84 ED
    jnz $+40                    ; 75 26

    cmp al, 0xF8                ; 3C F8
    jne $+3                     ; 75 01
        ; increment cl=depth
        inc ecx                 ; 41

    cmp al, 0xF9                ; 3C F9
    jne $+17                    ; 75 0F
        ; check depth = 0
        test cl, cl             ; 84 C9
        jz $+27                 ; 74 19
        ; decrement cl=depth
        dec ecx                 ; 49
        ; pop and check -1
        pop eax                 ; 58
        cmp al, 0               ; 3C 00
        jl $+5                  ; 7C 03
            push eax            ; 50
            jmp $+38            ; EB 24
        xor al, al              ; 30 C0

    test al, al                 ; 84 C0
    jnz $+11                    ; 75 09
        pop eax                 ; 58
        dec eax                 ; 48
        cmp al, -1              ; 3C FF
        jg $+3                  ; 7F 01
            inc eax             ; 40
        jmp $-11                ; EB F3
    push eax                    ; 50

    inc edx                     ; 42
    mov al, [edx]               ; 8A 02
    test al, al                 ; 84 C0
    jnz $-57                    ; 75 C5

    dec edx                     ; 4A

    ; in quote?
    test ch, ch                 ; 84 ED
    mov al, 0x22                ; B0 22
    jnz $-64                    ; 75 BE

    ; depth not zero?
    test cl, cl                 ; 84 C9
    mov al, 0x29                ; B0 29
    jnz $-70                    ; 75 B8

; pop base -1
pop edx                         ; 5A

; set return value based on ebp/esp comparison
xor eax, eax                    ; 31 C0
cmp ebp, esp                    ; 39 E5
jne $+3                         ; 75 01
inc eax                         ; 40
; restore esp
mov esp, ebp                    ; 89 EC
; restore ebp
pop ebp                         ; 5D
; return
ret                             ; C3

O código a seguir em C pode ser usado com o GCC em um sistema POSIX para testar:

#include <sys/mman.h>
#include <stdio.h>
#include <string.h>

int main(){
    char code[] = {
        0x8b, 0x54, 0x24, 0x04, 0x55, 0x89, 0xe5, 0x31, 0xc9, 0x6a, 0xff,
        0x8a, 0x02, 0x2c, 0x30, 0x3c, 0xf2, 0x75, 0x04, 0xf6, 0xd5, 0x30, 
        0xc0, 0x84, 0xed, 0x75, 0x26, 0x3c, 0xf8, 0x75, 0x01, 0x41, 0x3c, 
        0xf9, 0x75, 0x0f, 0x84, 0xc9, 0x74, 0x19, 0x49, 0x58, 0x3c, 0x00, 
        0x7c, 0x03, 0x50, 0xeb, 0x24, 0x30, 0xc0, 0x84, 0xc0, 0x75, 0x09, 
        0x58, 0x48, 0x3c, 0xff, 0x7f, 0x01, 0x40, 0xeb, 0xf3, 0x50, 0x42, 
        0x8a, 0x02, 0x84, 0xc0, 0x75, 0xc5, 0x4a, 0x84, 0xed, 0xb0, 0x22, 
        0x75, 0xbe, 0x84, 0xc9, 0xb0, 0x29, 0x75, 0xb8, 0x5a, 0x31, 0xc0, 
        0x39, 0xe5, 0x75, 0x01, 0x40, 0x89, 0xec, 0x5d, 0xc3,
    };
    void *mem = mmap(0, sizeof(code), PROT_WRITE|PROT_EXEC, MAP_ANON|MAP_PRIVATE, -1, 0);
    memcpy(mem, code, sizeof(code));
    int __cdecl (*test)(char *) = (int __cdecl (*)(char *)) mem;

    #define TRY(s) printf(s ": %d\n", test(s))

    printf("Truthy tests:\n");
    TRY("0");
    TRY(")");
    TRY("(");
    TRY("\"");
    TRY("()");
    TRY("\"\"");
    TRY("10");
    TRY("400010");
    TRY("210010");
    TRY("(\"\")00");
    TRY("3\"\"\"\"\"");
    TRY("(0)))0)1)0");
    TRY("2(2(2(0)0)0)0");
    TRY("2\"010\"\"44)()4\"");
    TRY(")31(0)0(201000100");
    TRY("())2)1))0\"3())\"))");
    TRY("3(\"4321(\"301(0)21100\"4\")\"123\"00)40\"121\"31000\"\"01010");

    printf("\nFalsy tests:\n");
    TRY("1");
    TRY("1(310");
    TRY("(1)0)");
    TRY("12(010");
    TRY("4\"00010\"");
    TRY("3120102100");
    TRY("20(2((0)(0)))");
    TRY("2(2(2(0)0)0)01)");
    TRY("4(0102)00)00000");
    TRY("2\"00\"(\"00\"2(\"\"))");

    munmap(mem, sizeof(code));
    return 0;
}

Python 2, 353 bytes

A função de análise percorre os tokens um de cada vez e cria uma árvore da estrutura do programa. Programas inválidos acionam uma exceção que causa a impressão de um zero (Falsy); caso contrário, a análise bem-sucedida resulta em um.

def h(f,k=0):
 b=[]
 if k:
  while f:b+=[h(f)]
  return b
 q=f.pop(0)
 if q==')':return[]
 elif q=='"':
  while f:
   q+=f.pop(0)
   if q[-1]=='"':break
 elif q=='(':
  while f:
   if f and f[0]==')':f.pop(0);break
   b+=h(f)
 else:
  for i in range(int(q)):b+=h(f)
  assert len(b)==int(q)
 return[[q,b]]
try:h(list(raw_input()));r=1
except:r=0
print r

A saída dos testes mostrando a saída do analisador:

------------------------------------------------------------
True: 0
    0

------------------------------------------------------------
True: )

------------------------------------------------------------
True: (
    (

------------------------------------------------------------
True: "
    "

------------------------------------------------------------
True: ()
    (

------------------------------------------------------------
True: ""
    ""

------------------------------------------------------------
True: 10
    1
        0

------------------------------------------------------------
True: 400010
    4
        0
        0
        0
        1
            0

------------------------------------------------------------
True: 210010
    2
        1
            0
        0
    1
        0

------------------------------------------------------------
True: ("")00
    (
        ""
    0
    0

------------------------------------------------------------
True: 3"""""
    3
        ""
        ""
        "

------------------------------------------------------------
True: 2(2(2(0)0)0)0
    2
        (
            2
                (
                    2
                        (
                            0
                        0
                0
        0

------------------------------------------------------------
True: 2"010""44)()4"
    2
        "010"
        "44)()4"

------------------------------------------------------------
True: )31(0)0(201000100
    3
        1
            (
                0
        0
        (
            2
                0
                1
                    0
            0
            0
            1
                0
            0

------------------------------------------------------------
True: 3("4321("301(0)21100"4")"123"00)40"121"31000""01010
    3
        (
            "4321("
            3
                0
                1
                    (
                        0
                2
                    1
                        1
                            0
                    0
            "4"
        "123"
        0
    0
    4
        0
        "121"
        3
            1
                0
            0
            0
        ""
    0
    1
        0
    1
        0

------------------------------------------------------------
False: 1
0
------------------------------------------------------------
False: 1(310
0
------------------------------------------------------------
False: 12(010
0
------------------------------------------------------------
False: 4"00010"
0
------------------------------------------------------------
False: 3120102100
0
------------------------------------------------------------
False: 20(2((0)(0)))
0
------------------------------------------------------------
False: 2(2(2(0)0)0)01)
0
------------------------------------------------------------
False: 4(0102)00)00000
0
------------------------------------------------------------
False: 2"00"("00"2(""))
0

O código antes do minificador:

def parse(tokens, first=False):
    toklist = []
    if first:
        while tokens :
            toklist += [parse(tokens)]
        return toklist
    tok = tokens.pop(0)
    if tok == ')' :
        return []
    elif tok == '"':
        while tokens:
            tok += tokens.pop(0)
            if tok[-1] == '"' :
                break
    elif tok == '(':
        while tokens:
            if tokens and tokens[0] == ')' :
                tokens.pop(0);
                break
            toklist += parse(tokens)
    else:
        for i in range(int(tok)) :
            toklist += parse(tokens)
        assert len(toklist) == int(tok)
    return [[tok, toklist]]

try :
    parse(list(raw_input()));
    r = 1
except :
    r = 0
print r

Pip , 88 72 bytes

Ideia retirada do CJam do Optimizer . Minha facada original no problema de um analisador de descida recursivo foi ... bastante mais longa.

Qpz:,5.iX,5AL'(.0X,#p.')p^:'"Fj,#pIj%2p@j:0p:Jpp.:')X#pL#ppR:z0!pRM')Rz0

Formatado, com explicação:

Qp                Query user for p
z:                Store the following list in z:
  ,5 . 0X,5         For x in range(5), concatenate x zeros to it
  AL                (append list)
  '(. 0X,#p .')     For x in range(len(p)), concatenate x zeros inside parens
p^: '"            Split p on " and assign result back to p
Fi,#p             Loop over the indices of the resulting list:
 Ii%2               If index is odd:
  p@i:0               Replace that item with 0
p: Jp             Concatenate the results and assign back to p
p.: ')X#p         Append len(p) closing parens to p
L#p               Loop len(p) times:
 pR:z0              Replace every occurrence in p of items of z with 0
! pRM')Rz0        Remove ) from result and replace z with 0 one more time; then
                  take logical negation, which will be true iff string is empty OR
                  consists only of zeros

Truques interessantes:

• Muitos operadores trabalham item-item em listas e intervalos. tão0X,5 , por exemplo, é 0 X [0 1 2 3 4] == ["" "0" "00" "000" "0000"].
• A partir de alguns dias atrás, o ternário Roperador moran Jr. pode ter uma lista para qualquer um dos seus argumentos: "abracadabra" R ["br" "ca"] 'bdáababdaba , por exemplo. Faço bom uso desse recurso zaqui.
• Os valores de falsidade no Pip incluem a sequência ""vazia [], a lista vazia e qualquer escalar que seja zero. Assim, 0é falso, mas também 0.0e "0000000". Às vezes, esse recurso é inconveniente (para testar se uma string está vazia, é preciso testar seu comprimento porque também "0"é falso), mas, para esse problema, é perfeito.

Javascript (ES6), 289 288 285 282 278 244 241 230 bytes

c=prompt(k="0"),j=c[l="length"];if((c.match(/"/g)||[])[l]%2)c+='"';c=c[R="replace"](/".*?"/g,k);c+=")".repeat(j);while(j--)c=c[R](/\(0*\)/,k)[R](/10/g,k)[R](/200/g,k)[R](/3000/g,k)[R](/40000/g,k);alert(!c[R](/0/g,"")[R](/\)/g,""))