Expressões entre parênteses

11

Hoje, seu desafio é produzir todos os parênteses completos possíveis de uma expressão.

Sua entrada é uma única linha de ASCII imprimível que contém um ou mais termos separados por operadores. A entrada também pode conter espaços - você deve ignorá-los. Um termo é [a-zA-Z0-9], um operador é [^ ()a-zA-Z0-9]. Você pode assumir que a entrada é sempre válida.

Saída de todas as formas possíveis entre parênteses completos da expressão especificada, separados por novas linhas com uma nova linha à direita opcional.

Fazer não :

  • Termos entre parênteses - somente entre parênteses os operadores.
  • Reordene os termos.
  • Saída de quaisquer espaços.

Exemplo de entrada / saída:

N
N

a * b
(a*b)

x_x_0
(x_(x_0))
((x_x)_0)

a * b|c|d
(a*(b|(c|d)))
(a*((b|c)|d))
((a*b)|(c|d))
((a*(b|c))|d)
(((a*b)|c)|d)

O menor código em bytes vence.

code-golf balanced-string orlp
fonte
Você deve listar exatamente os operadores que devemos considerar. É !um operador? Que tal ↑?
Optimizer
@Optimizer Listei a expressão regular exata do que é considerado um operador. !se ajusta ao regex, o mesmo acontece ↑, no entanto, ↑não pode fazer parte da entrada porque não é ASCII imprimível.
orlp
Ah ok. Então, qualquer coisa exceto um termo é um operador ...
Optimizer
Então, termos e operadores têm sempre um caractere?
user81655
1
insira trocadilho obrigatório relacionado ao LISP aqui
cat

Respostas:

2

Pitão, 38 bytes

L?tbsmmjj@bdk"()"*y<bdy>bhd:1lb2bjy-zd

Experimente online.

Ele define uma função recursiva que:

  • retorna a entrada se seu comprimento for 1
  • toma todas as duas divisões da entrada nos operadores e para cada divisão:
    • chama-se recursivamente em cada uma das metades
    • toma o produto cartesiano dos resultados de cada metade
    • une cada resultado pelo operador na divisão
    • entre parênteses o resultado associado
  • e finalmente concatena as matrizes resultantes.

A função é chamada com a sequência de entrada com espaços removidos e os resultados são unidos por novas linhas.

PurkkaKoodari
fonte
3

JavaScript (ES6), 208 197 bytes

s=>((q=x=>x.map((_,i)=>(a=[...x.slice(0,i*=2),p="("+x[i]+x[++i]+x[++i]+")",...x.slice(i+1)],x[i]?a[1]?q(a):r.push(p):0)))([...s.replace(/ /g,o="")],r=[]),r.map((l,i)=>r.indexOf(l)<i?0:o+=l+`
`),o)

Explicação

Usa uma função recursiva que pega uma matriz de [ t, o, t, o, etc... ]parênteses e cada par consecutivo de dois termos juntos [ (tot), o, etc... ]e repete esse processo até que haja apenas um elemento na matriz e filtra os valores duplicados.

s=>(                                  // s = input string
  (q=x=>                              // q = parenthesise array function
    x.map((_,i)=>(
      a=[                             // a = p with parenthesised pair of terms
        ...x.slice(0,i*=2),
        p="("+x[i]+x[++i]+x[++i]+")", // parenthesise and join 2 terms and an operator
        ...x.slice(i+1)
      ],
      x[i]?a[1]                       // make sure the loop is not over
        ?q(a)                         // check next level of permutations
        :r.push(p)                    // add the permutation to the results
      :0
    ))
  )([...s.replace(/ /g,               // remove spaces and parenthesise all expressions
    o="")],                           // o = output string
    r=[]),                            // r = array of result strings
  r.map(                              // filter out duplicates
    (l,i)=>r.indexOf(l)<i?0:o+=l+`
`
  ),o)                                // return o

Teste

Mostrar snippet de código

user81655
fonte