가 있는 몇 가지 질문 이 사이트에 괄호를 균형 및 브라켓 균형 여부 확인에 대한이. 균형 잡힌 괄호를 사용할 때가되었습니다!
수학과 프로그래밍에서 대괄호는 거품과 같습니다. 내부의 모든 것이 외부의 모든 것을 격리하여 내부의 모든 것이 평화롭게 일을 할 수 있고 외부의 모든 것이 하나의 객체 만 볼 수 있습니다. 그러나, 일련의 괄호는 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])
짧은 아이디어를 표현하기 위해 더 짧은 조건 을 사용합니다 : 루트 에서 문자열을 분할하십시오)(
. 예"(()(()))()"
를 들어["()(())", ""]
. -
우리는 분할의 각 부분을 처리 한 다음 모든 문자열을 수집하고 결합하여 올바른 출력을 얻습니다.
-
h
부품 목록v
을 처리합니다. 첫 번째 부품에 적용 되고 결과를 나머지 부품의 공정에 결합합니다. -
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 바이트!
설명
()
입력 문자열 에 각 쌍 의 인덱스 튜플 목록을 만듭니다 .- 다른
()
쌍 으로 둘러싸인 목록에서 튜플을 삭제하십시오 . - 나머지 튜플의 인덱스에서 끈을 자릅니다.
- 슬라이스 목록의 각 순열 목록을 작성하십시오.
- 인쇄 할 새 줄로 목록에 가입하십시오.
답변
자바 스크립트 (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 바이트
아니 코드 골프 포인트를 획득,하지만의 사용을 보여 Permutations
와 Distribute
이 문제에있다. 그러나 더 나은 접근법이있을 수 있습니다.
( 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}] &
중괄호 {
와를 사용하여 문자열로 입력하십시오 }
. 여러 줄 문자열을 출력합니다.