Wyrażenia w pełni nawiasowane

11

Dzisiaj Twoim wyzwaniem jest utworzenie wszystkich możliwych pełnych nawiasów wyrażenia.

Dane wejściowe to pojedynczy wiersz drukowalnego kodu ASCII zawierający jeden lub więcej terminów oddzielonych operatorami. Dane wejściowe mogą również zawierać spacje - należy je zignorować. Terminem jest [a-zA-Z0-9]operator [^ ()a-zA-Z0-9]. Możesz założyć, że dane wejściowe są zawsze prawidłowe.

Wyprowadza wszystkie możliwe sposoby pełnego nawiasowania danego wyrażenia, oddzielone znakami nowej linii z opcjonalnym znakiem końca linii.

Czy nie :

  • Warunki w nawiasach - tylko w nawiasach wokół operatorów.
  • Zmień kolejność warunków.
  • Wyprowadzaj dowolne spacje.

Przykładowe wejście / wyjście:

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)

Najmniejszy kod w bajtach wygrywa.

orlp
źródło
Musisz wymienić dokładnie operatorów, których musimy wziąć pod uwagę. Czy !operator? Co ?
Optymalizator
@Optimizer Podałem dokładne wyrażenie regularne tego, co uważane jest za operator. !pasuje do wyrażenia regularnego, tak robi , jednak nie może być częścią wkładu, ponieważ nie jest do druku ASCII.
lub
Ah, dobrze. Więc wszystko oprócz terminu jest operatorem ...
Optymalizator
Więc zarówno warunki, jak i operatory mają zawsze jeden znak?
user81655,
1
wstaw tutaj obowiązkową grę słów związaną z LISP
kot

Odpowiedzi:

2

Pyth, 38 bajtów

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

Wypróbuj online.

Definiuje funkcję rekurencyjną, która:

  • zwraca wartość wejściową, jeśli jej długość wynosi 1
  • pobiera wszystkie dwa podziały danych wejściowych na operatory i dla każdego podziału:
    • nazywa się rekurencyjnie na każdej z połówek
    • bierze iloczyn kartezjański wyników każdej połowy
    • łączy każdy wynik przez operatora podczas podziału
    • nawiasy łączące wynik
  • i na koniec konkatenuje powstałe tablice.

Następnie wywoływana jest funkcja z ciągiem wejściowym z usuniętymi spacjami, a do wyników dołączane są znaki nowej linii.

PurkkaKoodari
źródło
3

JavaScript (ES6), 208 197 bajtów

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)

Wyjaśnienie

Używa funkcji rekurencyjnej, która pobiera tablicę [ t, o, t, o, etc... ]i nawiasuje każdą kolejną parę dwóch terminów razem, podobnie jak [ (tot), o, etc... ]i powtarza ten proces, dopóki nie będzie tylko jednego elementu w tablicy, a następnie odfiltruje duplikaty wartości.

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

Test

użytkownik 81655
źródło