Parentheses Clusters

Write a program that groups a string into parentheses cluster. Each cluster should be balanced.

Examples :

split("((())d)") ➞ ["((()))"]

split("(h(e(l)l)o)(w(o)r)l(d)(w)h(a(t)(s)u)p") ➞ ["((()))", "(())", "()", "()", "(()())"]

split("((())())(()(()()))") ➞ ["((())())", "(()(()()))"]


Input may contain letters other than parentheses but you are not sorting them. (The possible characters in the input are uppercase and lowercase letters, numbers, and ())

Given parentheses will always be complete (i.e : ( will be matched with ) )

Cluster is when outermost ( ends with ). In short when your parentheses are all balanced at that moment so :

(((    ---> this will be balanced when 3 ) are added
)))    ---> now its balanced this is cluster 1
()     ---> this is cluster 2
(((((((((((((((((((((((((((((( ---> this is start of cluster 3. will need equal amount of ) to balance


This is code-golf, shortest code wins

(Link to challenge on Code Wars : link for those that wish to check it)

• This looks like it a pretty nice first challenge! For future reference, it's recommended to post challenges in the sandbox first to get feedback before posting them here. Sep 22 '21 at 14:42
• What is a cluster in this context? How exactly do we know where to split the string? Sep 22 '21 at 14:47
• @KevinCruijssen : yes, any printable ASCII, you are not sorting those brackets (should I add them to challenge ? Sep 22 '21 at 14:56
• Do you have permission to repost the challenge verbatim from Codewars?
– xnor
Sep 22 '21 at 15:04
• I guess it's fine if it's your challenge and isn't actually open on the other site, though I don't know if there are still content licensing issues. Yes, I think linking it would be good.
– xnor
Sep 22 '21 at 15:14

Vim, 20 bytes

:s/\w//g
qq%a
<Esc>@qq@q


Try it online!

Programmer's text editor builtins ftw! \o/

Explanation:

:s/\w//g    # Remove all letters and numbers
qq          # Start macro 'q'
%a        #  Jump to matching parenthesis and insert newline
<Esc>
@q     #  Call macro 'q'
q    #  End macro 'q'
@q  # Call macro 'q'

• @KevinCruijssen That's how it was at first, but it was edited: "(The possible characters in the input are uppercase and lowercase letters, numbers, and ())" Sep 22 '21 at 15:35
• Ah, hadn't noticed the challenge changed. When I asked earlier OP mentioned all printable ASCII is possible in the input.. :/ Ah well, in that case I can golf a byte in my own answer as well. ;) Sep 22 '21 at 15:39

J, 35 bytes

(](]<;.2~0=[:+/\_1+2*i.)[-.-.)&'()'


Try it online!

• Remove all parens from the input.
• Turn ( into -1 and ) into 1, and take the scan sum, then convert that into a mask which is 1 wherever the sum is 0.
• Finally, use that mask to cut the cleaned input into chunks.

Jelly, 11 bytes

fØ(µO-*Ä¬Ṗk


Try it online!

The Footer just runs all the test cases, joins each cluster by a single newline and each test case by 2.

How it works

fØ(µO-*Ä¬Ṗk - Main link. Takes a string S on the left
fØ(         - Remove all non-"()" characters
µ        - Use this string of parentheses P as the argument from here:
O       - Convert to ords ("(" -> 40, ")" -> 41)
-*     - Raise -1 to that power, yielding "(" -> 1, ")" -> -1
Ä    - Cumulative sum
¬   - Logical NOT, converting 0 -> 1, everything else -> 0
Ṗ  - Remove the trailing 1
k - Split P at the indices of the 1s


APL(Dyalog Unicode), 26 bytes SBCS

{⍵⊂⍨¯1⌽0=+\¯1*')'=⍵}∩∘'()'


∩∘'()' intersect right argument with (). This removes all other characters.
{ ... } call the dfn with the cleaned string as its right argument ⍵.

')'=⍵ for each character in the string, is it equal to )?
¯1* this maps ( to 1 and ) to ¯1.
+\ cumulative sums. This is the nesting level for each character.
0= equal to 0?
¯1⌽ rotate the trailing 1 to the front.
⍵⊂⍨ partition the string at characters with nesting level 0.

Python 3, 75 bytes

def f(s,x=1):
for i in s:y=(i==")")-(i=="(");x+=y;y and print(i,end=" "*x)


Try it online!

prints the clusters separated by spaces

Python 3, 88 bytes

def f(s,x=1,w=""):
for i in s:y=(i==")")-(i=="(");x+=y;w+=y*y*i+" "*x
return w.split()


Try it online!

returns a list of clusters

05AB1E, 1817 14 bytes

žuÃDÇÈ·<.¥_Å¡¦


-1 byte because of the rule change from all printable ASCII to just parenthesis and alphanumeric characters in the input
-3 bytes and improved performance thanks to @cairdCoinheringaahing

Output as a list of list of characters.

Explanation:

žu              # Push constant string "()<>[]{}"
Ã             # Only keep those characters from the (implicit) input-string
D            # Duplicate this string
Ç           # Convert each character in the copy to its unicode integer:
#  "("→0; ")"→1
É          #  Check for each whether it's odd: "("→0; ")"→1
·         #  Double each: "("→0; ")"→2
<        #  Decrease each by 1: "("→-1; ")"→1
.¥      #  Undelta this list
_     #  Check for each whether it's equal to 0 (1 if 0; 0 otherwise)
Å¡   # Split the string we've duplicated at the truthy indices,
# which implicitly converts the parts to character-lists
¦  # And remove the leading empty list
# (after which the result is output implicitly)

• 14 bytes (and a lot faster), but I'm sure you can golf it a bit Sep 22 '21 at 16:22
• In fact, if you can do -1 * ord(char) in 2 bytes, you can golf the È·< bit Sep 22 '21 at 16:40
• @cairdcoinheringaahing Thanks for the -3, but I'm not sure I follow your second command. -1 * ord(char) would simply be Ç(, but The .¥ won't work with -40/-41 instead of -1/1. Sep 22 '21 at 16:44
• Oh right, I was thinking in Jelly terms, where * is power, not multiplication (so raising -1 to the power of the ordinals) Sep 22 '21 at 16:44
• @cairdcoinheringaahing Ah ok, I usually use ** or ^ for that. ;) But I'm afraid I won't be able to do that in 2 bytes here. È·< would be ®sm in that case. Sep 22 '21 at 16:52

Ruby, 37 bytes

->s{s.tr('^()','').scan /$$\g<0>*$$/}


Try it online!

Returns an array of clusters. The numbered subpattern \g<0> nests the balanced-parentheses-matching regex within itself.

Japt v2.0a0, 1513 12 bytes

r\w ó@T±JpXc


Try it

r\w ó@T±JpXc     :Implicit input of string U
r                :Replace
\w              :  RegEx /[a-z0-9]/gi
ó            :Partition after each character X
@           :That returns falsey (0) when passed through the following function
T±         :  Increment T (initially 0) by
J        :  -1
p       :  Raised to the power of
Xc     :  Charcode of X


JavaScript (ES6),  61 60  59 bytes

Saved 1 byte thanks to @tsh

Outputs a string with one cluster per line.

s=>s.replace(/./g,c=>c=='('?(s=-~s,c):c==')'?--s?c:)
:'')


Try it online!

• c+"\n" ->")\n"
– tsh
Sep 23 '21 at 1:18

Pip, 282524 23 bytes

Fca@X^pI$==_NyPBcMpY/Py  Try it here! Or, with a variable definition in the header, you can also Try it online! Explanation Pushes one parenthesis at a time onto y, checks whether y is balanced, and if so, outputs and resets it. Fca@X^pI$==_NyPBcMpY/Py
a is cmdline arg; p is "()"; y is "" (implicit)
Fc                       For each character c in
a@                     each regex match in a of
X                    a regex matching
^                   either of the characters in
p                  "()":
I                  If
yPBc         we push c onto the end of y
_N             and then the number of occurrences in y of
Mp       each character in "()"
$== is equal: Py Print y / and invert (resulting in nil because y isn't a number) Y and yank that as the new value of y  This works because pushing a string onto a variable that is nil sets the variable to the pushed string, the same as if the variable's value had been "". Java 8, 8982 81 bytes s->{int t=0;for(var c:s)System.out.print(c==40?++t>0?c:c:c==41?--t<1?") ":c:"");}  -7 bytes thanks to @ZaelinGoodman Input as character-array; output as a space-delimited string. Try it online. Explanation: s->{ // Method with character-array as parameter and no return int t=0; // Create a temp integer, starting at 0 for(var c:s) // Loop over the characters of the input-array: System.out.print( // Print: c==40? // If the current character is '(': ++t // Increase t by 1 >0?c:c // And print the '(' :c==41? // Else-if the current character is ')': --t // Decrease t by 1 <1? // If it is now 0: ") " // Print the ')', plus a space : // Else (it's not 0): c // Print just the ')' : // Else (it's a different character): "");} // Print nothing  • Sep 22 '21 at 17:41 • 82 bytes! Try it Online! Sep 22 '21 at 20:13 • @ZaelinGoodman Thanks. :) Sep 22 '21 at 20:35 JavaScript (Node.js), 83 bytes A=>[...A.replace(/[^()]/g,(o=0,t=''))].map(l=>(t+=l,!(o+=l<")"||-1)&&t+(t="")||""))  Try it online! If it accepts array having , in between parentheses otherwise : JavaScript (Node.js), 101100 95 bytes A=>[...A.replace(/[^()]/g,(o=0,a=[],t=''))].map(l=>(o+=l<")"||-1,t+=l,!o&&a.push(t+(t=''))))&&a  Try it online! • @wasif : na. I already saw this challenge on some other site (it seems OP copy pasted his own challenge on two sites, and solved that one. I'll link it). my own solution is from that challenge. There you go the challenge : Sep 22 '21 at 14:57 • @wasif : codewars.com/kata/614b02aab2d61200476973e9 It's identical to that one. and I just solved it 20-30 mins ago, hardly going to forget that :) Sep 22 '21 at 14:59 • Ok sorry, take my apologies Sep 22 '21 at 15:00 • @wasif : no problem, I'll admit its hella sus. but since I had already solved it I merely had to copy paste my own solution here Sep 22 '21 at 15:02 Java (JDK), 8680 79 bytes n->{int o=0;for(var c:n)if(o!=(o+=c>41?0:81-2*c))System.out.print(o<1?") ":c);}  Try it online! -7 thanks to Kevin Kruijssn and Zaelin Goodman! • Nice different approach, +1 from me. :) You can golf the char to var for -1. Sep 22 '21 at 18:01 • 81 bytes! Sep 22 '21 at 18:57 • @ZaelinGoodman That can be 80 bytes with the same golf I suggested in my comment above: char to var. :) Sep 22 '21 at 20:35 • Edited! Thanks for the help! Sep 23 '21 at 5:18 • c+" " can be ") " for another -1 byte Sep 24 '21 at 7:48 JavaScript, 55 53 bytes Outputs a space delimited string with a trailing space. s=>s.replace(/./g,x=>x>{}?:(n+=x>s||-1)?x:) ,n=0)  Try it online! Perl 5, 26 bytes y/()//cd;s/$$(?R)*$$/$&
/g


Try it online!

y/()//cd;           #delete all chars from input line except ( and )
s/$$(?R)*$$/$& #print clusters separated by newline /g #found by recursive regexp with (?R)  PowerShell Core, 89 80 bytes -9 bytes thanks to @mazzy!!! $args-replace"\w"|sls "($$(?=\(*(?<S>$$))|\k<S>(?<-S>))+?(?(S)(?!))"-a|% M*|% V*


Try it online!

• Try it online? Sep 23 '21 at 19:50
• @mazzy nice, thanks! Been away from the community too long, my golfing skills got rusty :) Sep 24 '21 at 14:19

PowerShell, 62 bytes

switch($args){'('{$r+=$_;++$l}')'{$r+=$_;if(!--$l){$r;\$r=''}}}


Try it online!

C (gcc), 70 bytes

I think at this point I have to admit I'm on a ternary operator abuse spree.

Big thanks to ErikF for -14 bytes.

And thanks the ceilingcat for -4 more!

c;f(d){for(d=0;read(0,&c,1);c>47||(d+=2*putchar(c)-81)||putchar(32));}


Try it online!

• 74 bytes Try it online! Sep 23 '21 at 6:20
• Nice golfing! lol I stared at this a long time thinking there's nothing else to do Sep 24 '21 at 1:08
• An interesting thing about putchar is that it returns the character that was passed to it. Sometimes handy in golfing, rarely so in real life! :-) Sep 24 '21 at 1:47

R, 99 92 bytes

Or R>=4.1, 85 bytes by replacing the word function with \.

-7 bytes thanks to @Dominic van Essen.

function(s,x=utf8ToInt(s))Map(intToUtf8,split(a<-x[x<42],head(diffinv(!cumsum(a*2-81)),-1)))


Try it online!

As always, R is terrible in string challenges...

• Nice! Map & diffinv can save a few bytes... Sep 30 '21 at 22:49
• @DominicvanEssen, thanks! The Map trick is something I should have remembered, but using diffinv - that's really clever (I think I've never used this function before). Oct 1 '21 at 6:31

Lua, 46 bytes

print(arg[1]:gsub("%w",""):gsub("%b()","%1;"))


Try it online!

Looks like it happened working. Though I don't know much about Lua.

Retina 0.8.2, 25 bytes

\w

!\(((\()|(?<-2>.))*.


Try it online! Link includes test cases. Explanation: The first two lines simply delete letters and digits. The final line matches groups of (assumed) parentheses. .NET balancing groups keep track of the number of unmatched (s and don't allow more )s than (s. This means that the inner loop stops when it reaches the matching ) for the outer (. The ! causes the groups themselves to be output on separate lines.

Charcoal, 19 bytes

ＦＳ≡ι(«ι⊞υυ»)«ι¿¬⊟υ⸿


Try it online! Link is to verbose version of code. Explanation:

ＦＳ≡ι


Switch over each character of the input string.

(«ι⊞υυ»


If it's a ( then print it and push the predefined empty list to itself. The list therefore contains itself as many times as there are unbalanced (s.

)«ι


If it's a ) then print it, and...

¿¬⊟υ⸿
`

... if popping the list leaves it empty again then move to the next line.