브래킷을 버블 링하십시오! 거품 임에도

있는 몇 가지 질문 이 사이트에 괄호를 균형 및 브라켓 균형 여부 확인에 대한이. 균형 잡힌 괄호를 사용할 때가되었습니다!

수학과 프로그래밍에서 대괄호는 거품과 같습니다. 내부의 모든 것이 외부의 모든 것을 격리하여 내부의 모든 것이 평화롭게 일을 할 수 있고 외부의 모든 것이 하나의 객체 만 볼 수 있습니다. 그러나, 일련의 괄호는 1 차원 인 반면, 기포는 일반적으로 2 차원 이상이다. 즉, 거품이 서로 닿거나 다른 거품의 내부와 외부를 교차하지 않는 한 거품이 서로 자유롭게 움직일 수 있습니다.

도전

입력 값은 round (), square [], curly {}또는 angle 단일 유형의 일치하는 대괄호 문자열입니다 <>. 프로그램이 어떤 종류의 프로그램을 받아들이 길 원하는지는 사용자에게 달려 있으며 한 종류의 대괄호 만 허용하는 프로그램이 허용됩니다. (프로그램이 그 중 하나를 처리 할 수있는 경우 가상 보너스, 동일한 입력에서 모든 것을 처리 할 수있는 경우 큰 가상의 보너스 포인트) 입력 공백은 허용되지만 대괄호 사이에는 아무 것도 포함 할 수 없습니다.

출력은 두 개의 동일한 스트링없이 동일한 기포 구성을 생성하는 브래킷의 가능한 모든 재구성 (임의의 순서로, 그리고 원래 입력을 포함하여)입니다. 즉 ()(), ()()기술적으로 장소를 바꿀 수있는 두 개의 거품 임에도 불구하고의 입력을 사용 하면 출력도 단지 임을 의미합니다. 거대한 상상력 보너스의 경우, {}[]()의지의 입력은 물론 6 가지 요소 / 문자열 / 라인의 출력으로 이어집니다.

기포가 다른 기포 내부에서 외부로 또는 외부에서 내부로 교차하지 않고 기포를 움직여서 하나를 다른 기포로 만들 수 있다면 기포의 두 가지 구성은 “동일”합니다. 중첩 된 괄호를 트리에 비유 한 경우 (각 일치하는 쌍은 하나의 노드이고, 내의 모든 일치하는 쌍은 하위 노드이며, 그 안에있는 각 일치하는 쌍은 다시 하위 노드가있는 등) 지정된 노드의 하위 노드가 정렬 된 경우 버블의 단일 구성은 노드가 정렬되지 않은 트리입니다.

문자열 목록 또는 단일 문자 목록 또는 공백이있는 단일 문자열을 반환 stdout하거나 stderr사이에 공백 문자 (가장 일반적으로 줄 바꿈 또는 공백) 형식으로 인쇄하는 등의 합리적인 출력 형식이 수행됩니다. 각 재구성.

실제 출력 전후에 각 재구성 및 후행 및 선행 개행 / 빈 목록 요소에 대한 후행 공백이 있습니다. 입력에서 허용하는 것과 동일한 종류의 괄호를 출력에 사용해야합니다. 여기에 지정된 대괄호, 줄 바꿈 및 공백 및 사용하는 구분 기호를 제외하고 인쇄되지 않아야합니다 (가시 / 제로 너비 문자 포함).

점수는 코드의 바이트 수입니다. 각 언어 당 가장 적은 수의 승리. 당신은 당신의 상상 보너스를 정기적으로 또는 대규모로받을 수 있는지에 주목할 수 있지만, 점수에는 영향을 미치지 않습니다. 실제 보너스는 균형을 맞추기가 너무 어렵습니다.

입출력 예

예 1 :

입력:

()(())

산출:

()(())
(())()

예 2 :

입력:

(()())()()

산출:

(()())()()
()(()())()
()()(()())

예 3 :

입력:

(()(()))()

산출:

((())())()
()((())())
(()(()))()
()(()(()))


답변

CJam , 18 바이트

{~{_{{B}%e!}&}:B~}

온라인으로 사용해보십시오!

Business Cat 덕분에 -2 .

을 포함하는 문자열로 입력을받습니다 []. 순열 목록을 반환합니다 (빈 목록은 CJam의 빈 문자열과 같으므로을 []얻는 대신 "").


답변

하스켈 , 227 210 208 205 바이트

import Data.List
l=last
a!x=init a++[l a++[x]]
h[]=[""]
h(x:y)=["("++z++")"++t|z<-v x,t<-h y]
g(a,r)x|x=='('=(a+1,l$(r++h[]):[r!x|a>0])|1>0=(a-1,l$r:[r!x|a>1])
v s=nub$h=<<(permutations.snd$foldl g(0,[])s)

온라인으로 사용해보십시오!

이것은 힘들었다!

약간 골프

Laikoni 덕분에 2 바이트 절약

Bruce Forte 덕분에 2 바이트 절약

이것이 모든 경우에 작동하는지 잘 모르겠습니다. 몇 가지 설명 :

  • a!x에서 문자열 x의 마지막 목록에 문자열 을 추가하십시오 a(a 유형 [[String]])

  • snd$foldl(\(a,r)x->if x=='('then(a+1,last$(r++[[]]):[r!x|a>0])else(a-1,last$r:[r!x|a>1])짧은 아이디어를 표현하기 위해 더 짧은 조건 을 사용합니다 : 루트 에서 문자열을 분할하십시오 )(. 예 "(()(()))()"를 들어 ["()(())", ""].

  • 우리는 분할의 각 부분을 처리 한 다음 모든 문자열을 수집하고 결합하여 올바른 출력을 얻습니다.

    1. h부품 목록 v을 처리합니다. 첫 번째 부품에 적용 되고 결과를 나머지 부품의 공정에 결합합니다.

    2. v 부품의 각 순열에 대한 결과를 집계하고 중복을 제거합니다.

더 넓은 뷰를 추가하려면 기본적으로 빈 노드가있는 트리 (이진 트리가 아님)가 있습니다. 남겨주세요 (). 각 노드에 대해 분기의 모든 순열을 생성해야하지만 노드에서 분기를 가져 와서 다른 노드에 배치 할 수는 없습니다. 나는 깊이 처음으로 검색을 수행했습니다.


답변

파이썬 2, 353 350 331 바이트

s=input()
f=lambda i,t=0:i+1if t<0else f(i+1,t-1)if"("<s[i+1]else f(i+1,t+1)
c=[(x,f(x))for x in range(len(s))if")">s[x]]
p=lambda l:[[]]if len(l)<1else[x for y in p(l[1:])for x in[y[:i]+[l[0]]+y[i:]for i in range(len(y)+1)]]
print[''.join(x)for x in p([s[c[x][0]:c[x][1]]for x in range(len(c))if all(c[x][1]>y[1]for y in c[:x])])]

()입력으로 문자열을 수신 하고 결과를 인쇄합니다.

여기 사용해보십시오!

내가 사용을 피할 itertools.permutations도움으로 파올로의 에 대한 답변 이 질문에 .

에게 감사 비즈니스 고양이 3 바이트를 찾기 위해, 그리고 당신을 감사합니다 씨 Xcoder 놀라운 19 바이트!

설명

  1. ()입력 문자열 에 각 쌍 의 인덱스 튜플 목록을 만듭니다 .
  2. 다른 ()쌍 으로 둘러싸인 목록에서 튜플을 삭제하십시오 .
  3. 나머지 튜플의 인덱스에서 끈을 자릅니다.
  4. 슬라이스 목록의 각 순열 목록을 작성하십시오.
  5. 인쇄 할 새 줄로 목록에 가입하십시오.

답변

자바 스크립트 (Firefox 30-57), 222 바이트

s=>(g=a=>a+a?[for(x of g(a[0]))for(y of a.keys())for(z of g(a.slice(1)))(z.splice(y,0,x),z)]:[a])(eval(`[${s.replace(/]\[/g,`],[`)}]`)).map(g=a=>`[`+a.map(g).join``+`]`).sort().filter(s=>t<(t=s),t=``).map(s=>s.slice(1,-1))

[]문자열을 취 합니다. 설명:

s=>(                                Inner function to permute an array
 g=a=>a+a?[                         If array is not empty
  for(x of g(a[0]))                 Permute the first element of the array
  for(y of a.keys())                Generate a list of insertion points
  for(z of g(a.slice(1)))           Permute the rest of the array
  (z.splice(y,0,x),z)]:             Make all possible permutations
  [a]                               Otherwise return a list of an empty array
)(eval(`[${                         Convert the string to a nested array
   s.replace(/]\[/g,`],[`)}]`)      ... inserting commas where necessary
).map(                              Process the results
 g=a=>`[`+a.map(g).join``+`]`       Recursively convert back to string
).sort().filter(s=>t<(t=s),t=``     Check for duplicates
).map(s=>s.slice(1,-1))             Remove outer `[]`s

답변

수학, 337 바이트

아니 코드 골프 포인트를 획득,하지만의 사용을 보여 PermutationsDistribute이 문제에있다. 그러나 더 나은 접근법이있을 수 있습니다.

( seq: 순서, alt: 대안)

SetAttributes[alt, {Flat, OneIdentity}]
StringTake[
  StringReplace[ToString[
    ToExpression["{" <> StringReplace[#, "}{" -> "},{"] <> "}"]
        /. List -> Permutations@*seq
       /. List -> alt
      /. seq -> (Distribute[seq@##, alt] &)
     /. {seq -> List, alt -> Alternatives}],
   {", " -> "", "} | {" -> "\n"}],
  {2, -2}] &

중괄호 {와를 사용하여 문자열로 입력하십시오 }. 여러 줄 문자열을 출력합니다.