# Telescopic Parentheses

Consider a non-empty string of correctly balanced parentheses:

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


We can imagine that each pair of parentheses represents a ring in a collapsed telescopic construction. So let's extend the telescope:

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


Another way to look at it is that the parentheses at depth n are moved to line n, while keeping their horizontal position.

Your task is to take such a string of balanced parentheses and produce the extended version.

You may write a program or function, taking input via STDIN (or closest equivalent), command-line argument or function parameter, and producing output via STDOUT (or closest equivalent), return value or function (out) parameter.

You may assume that the input string is valid, i.e. consists only parentheses, which are correctly balanced.

You may print trailing spaces on each line, but not any more leading spaces than necessary. In total the lines must not be longer than twice the length of the input string. You may optionally print a single trailing newline.

## Examples

In addition to the above example, here are a few more test cases (input and output are separated by an empty line).

()

()

(((())))

(      )
(    )
(  )
()

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

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

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

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


Related Challenges:

• Topographic Strings, which asks you to produce what is essentially the complement of the output in this challenge.
• Code Explanation Formatter, a broad generalisation of the ideas in this challenge, posted recently by PhiNotPi. (In fact, PhiNotPi's original description of his idea was what inspired this challenge.)

Huh, this got quite a lot of participation, so here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

# Language Name, N bytes


where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

# Ruby, <s>104</s> <s>101</s> 96 bytes


function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function getAnswers(){$.ajax({url:answersUrl(page++),method:"get",dataType:"jsonp",crossDomain:true,success:function(e){answers.push.apply(answers,e.items);if(e.has_more)getAnswers();else process()}})}function shouldHaveHeading(e){var t=false;var n=e.body_markdown.split("\n");try{t|=/^#/.test(e.body_markdown);t|=["-","="].indexOf(n[1][0])>-1;t&=LANGUAGE_REG.test(e.body_markdown)}catch(r){}return t}function shouldHaveScore(e){var t=false;try{t|=SIZE_REG.test(e.body_markdown.split("\n")[0])}catch(n){}return t}function getAuthorName(e){return e.owner.display_name}function process(){answers=answers.filter(shouldHaveScore).filter(shouldHaveHeading);answers.sort(function(e,t){var n=+(e.body_markdown.split("\n")[0].match(SIZE_REG)||[Infinity])[0],r=+(t.body_markdown.split("\n")[0].match(SIZE_REG)||[Infinity])[0];return n-r});var e={};var t=0,c=0,p=-1;answers.forEach(function(n){var r=n.body_markdown.split("\n")[0];var i=$("#answer-template").html();var s=r.match(NUMBER_REG)[0];var o=(r.match(SIZE_REG)||[0])[0];var u=r.match(LANGUAGE_REG)[1];var a=getAuthorName(n);t++;c=p==o?c:t;i=i.replace("{{PLACE}}",c+".").replace("{{NAME}}",a).replace("{{LANGUAGE}}",u).replace("{{SIZE}}",o).replace("{{LINK}}",n.share_link);i=$(i);p=o;$("#answers").append(i);e[u]=e[u]||{lang:u,user:a,size:o,link:n.share_link}});var n=[];for(var r in e)if(e.hasOwnProperty(r))n.push(e[r]);n.sort(function(e,t){if(e.lang>t.lang)return 1;if(e.lang<t.lang)return-1;return 0});for(var i=0;i<n.length;++i){var s=$("#language-template").html();var r=n[i];s=s.replace("{{LANGUAGE}}",r.lang).replace("{{NAME}}",r.user).replace("{{SIZE}}",r.size).replace("{{LINK}}",r.link);s=$(s);$("#languages").append(s)}}var QUESTION_ID=49042;var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";var answers=[],page=1;getAnswers();var SIZE_REG=/\d+(?=[^\d&]*(?:&lt;(?:s&gt;[^&]*&lt;\/s&gt;|[^&]+&gt;)[^\d&]*)*$)/;var NUMBER_REG=/\d+/;var LANGUAGE_REG=/^#*\s*([^,]+)/
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src=https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js></script><link rel=stylesheet type=text/css href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"><div id=answer-list><h2>Leaderboard</h2><table class=answer-list><thead><tr><td></td><td>Author<td>Language<td>Size<tbody id=answers></table></div><div id=language-list><h2>Winners by Language</h2><table class=language-list><thead><tr><td>Language<td>User<td>Score<tbody id=languages></table></div><table style=display:none><tbody id=answer-template><tr><td>{{PLACE}}</td><td>{{NAME}}<td>{{LANGUAGE}}<td>{{SIZE}}<td><a href={{LINK}}>Link</a></table><table style=display:none><tbody id=language-template><tr><td>{{LANGUAGE}}<td>{{NAME}}<td>{{SIZE}}<td><a href={{LINK}}>Link</a></table>

• Alternative title: De-Lisp-ify a string. :P Apr 20 '15 at 20:25
• Are there any restrictions on the color of the output? Apr 21 '15 at 20:20
• @MartinBüttner: nevermind, I found a cleaner way; let's just say that my previous idea would have shaved a byte leaving all the closed parentheses blinking blue over cyan... :-) Apr 21 '15 at 21:00
• @MatteoItalia oh god, I'm glad that didn't happen. ;) Apr 21 '15 at 21:00
• @MatteoItalia: Post that version! It's worth seeing. Apr 22 '15 at 4:28

# 05AB1E, 14 11 bytes

2IDÇÉü+>4αΛ


Try it online.

Explanation:

2        # Push 2
I        # Push the input-string
D        # Create a copy of the input-string,
Ç       # and convert it to a list of codepoint integers: ")"→41; "("→40
É      # Check for each if it's odd: ")"→1; "("→0
ü     # For each overlapping pair:
+    #  Add them together: "(("→0; "()"→1; ")("→1; "))"→2
>   # Increase each by 1: "(("→1; "()"→2; ")("→2; "))"→3
4α # Take the absolute difference with 4: "(("→3; "()"→2; ")("→2; "))"→1
Λ        # Use the Canvas builtin with the given three arguments:
#  - Directions: the list of 123 we created, for ↗→↘ respectively
#  - What to draw: the third remaining copy of the input-string
#  - Line-lengths per step: the 2


Here a step-by-step explanation of the output for input (()(()())()((())))(()):

Preparation step: the overlapping pairs are ["((","()",")(","((","()",")(","()","))",")(","()",")(","((","((","()","))","))","))",")(","((","()","))"], which are mapped with DÇÉü+>4α to [3,2,2,3,2,2,2,1,2,2,2,3,3,2,1,1,1,2,3,2,1], which indicate the directions [↘,→,→,↘,→,→,→,↗,→,→,→,↘,↘,→,↗,↗,↗,→,↘,→,↗]:

7   0   1
↖ ↑ ↗
6 ← X → 2
↙ ↓ ↘
5   4   3


When we use the Canvas builtin, it then draws like this:

Step 1: draw 2 characters ((() in direction 3 (↘):

(
(


Step 2: draw 2-1 characters ()) in direction 2 (→):

(
()


Step 3: draw 2-1 characters (() in direction 2 (→):

(
()(


Step 4: draw 2-1 characters (() in direction 3 (↘):

(
()(
(


Etc.

For an in-depth explanation of the Canvas builtin I can refer to this 05AB1E tip of mine.

# Pip-l, 23 22 bytes

sX{%Aa?DiUi-1}._MaZD:s


Try it here! Or, here's a 25-byte equivalent in Pip Classic: Try it online!

### Reminiscence

Pip, old chap, how far we've come.

This clunky 53-byter was my first Pip answer on this site, over six years ago. I'd like to leave that answer untouched as a historical artifact, so I'm posting my modern Pip solution here separately. It's pretty clear that the two are different languages anyway. The old solution doesn't even work in modern Pip (though it still does on the TIO version).

### Explanation

sX{%Aa?DiUi-1}._MaZD:s
s is space; i is 0; a is command-line arg (implicit)
Ma      Map this function to each character in the argument:
{ Aa       }            The ASCII code of the character
%                      Mod 2
?                   Is that truthy (1, close paren) or falsey (0, open paren)?
Di                  If truthy, decrement i and return it
Ui                If falsey, increment i
-1              and return i-1 (i.e. the previous value of i)
sX                        Make a string of that many spaces
._          Concatenate the parenthesis to it
ZD:   Zip the list of strings to transpose it, padding to a rectangle
s  using spaces
Autoprint (implicit), each sublist on its own line (-l flag)


n _ []=[]
n h ('(':r)=('(',h):n(h+1)r
n d (')':r)=let h=d-1 in(')',h):n h r
m n []=n
m n ((_,h):r)=m(max h n)r
p s=let v=n 0 s;h=m 0 v;in map(\d->map($$b,l)->if l==d then b else ' ')v)[0..h] main=fmap p getLine>>=mapM_ putStrLn  • You can save a few spaces with operators: e.g. n#[] instead of m n []. Apr 25 '15 at 17:02 # Perl, 76 bytes a[/\(/?l++:--l][i++]=_ for split//,<>;print map{_||' '}@_,"\n"for@a  No use strict here :) # Lex, 94 bytes Depends on Linux console codes. With gcc, you can cut out four bytes by replacing both instances of \33 with an actual escape character. %% int p[2]={0}; \( printf("(\33D");++p[!*p];$$ printf("\33M)");--*p;
\n while(p[1]--)ECHO;


To compile and run:

$flex -o telescopic.c telescopic.l$ gcc -o telecopic telescopic.c -lfl
$./telescopic (()(()())()((())))(()) ( )( ) ()( )()( ) () ()() ( ) () --- type ctrl-D ---  # IDL 8.4, 173 177 bytes This is similar enough to the formatter challenge that I had half a solution already. IDL is still a terrible golfing language, but I'm pretty happy with how this worked out. read,(p='')&a=[0:strlen(p)-1]&c=strmid(p,a,1)&e=c.map(lambda(x,d:'('eq x:d++:d---1)))&print,[0:max(e)].map(lambda(x,y,z:y.reduce(lambda(t,u,v,w,:t+(w eq v?u:' ')),x,z),c,a))&end  Un-golfed: read,(p='') ;read a string from input a=[0:strlen(p)-1] ;index array to the input c=strmid(p,a,1) ;split the input into an array of 1-char substrings e=c.map(lambda(x,d:'('eq x:d++:d---1))) ;for each substring, increment depth if ( and decrement otherwise, saving depth each time print,[0:max(e)].map(lambda(x,y,z:y.reduce(lambda(t,u,v,w,:t+(w eq v?u:' ')),x,z),c,a)) ;print an array of strings, each one including the parens in that depth level. end ;end the script  # C#, 196 bytes Very simple complete program that takes input via STDIN, and outputs to STDOUT. I should like to get rid of the S.Length, but haven't found a way that pays. using Q=System.Console;class P{static void Main(){var S=Q.ReadLine();for(int i=0,c;++i<S.Length;){var r="";c=0;foreach(var k in S)r+=(c+=81-k*2)+k-40==i?k:' ';if(r.Contains("("))Q.WriteLine(r);}}}  It simply iterates over the input a number of times (input length - 1), keeping track of the parentheses "depth", and comparing it to the current iteration count (i) - if they match, then it adds the current parenthesis to a string, to be printed at the end of the iteration. Because more iterations may be done than necessary, it only prints the iteration result (r) if it contains a parenthesis. using Q=System.Console; class P { static void Main() { var S=Q.ReadLine(); // read input for(int i=0,c; ++i<S.Length; // can't be more than S.Length - 1 lines of output ) { var r=""; // reset result c=0; // current paren depth foreach(var k in S) // for each char in input r+= // append something... (c+=81-k*2) // move c +k-40==i? // check if we should output the current char k: ' '; // otherwise a space if(r.Contains("(")) // only print if there is some content Q.WriteLine(r); } } }  # Python 2, 166 bytes Not much to be said: m,c,l=list(input()),0,[] for j in m:c+=1if j=='('else-1;l+=[c-1if j=='('else c] for i in range(max(l)+1): t,p='',0 for q in m:t+=q if l[p]==i else' ';p+=1 print t  # MATL, 42 41 bytes Uses current version (4.0.0) of the language, which is newer than this challenge (but the challenge was so attractive...) j32-t8=2*1-TTo3X53$X+ZSYsP0hP1+wtn:wZ?32+c


EDIT (May 20, 2016): Try it online! with X+ replaced by Y+, according to version 18.0.0 of the language.

>> matl j32-t8=2*1-TTo3X53$X+ZSYs0wh1+wtn:wZ?32+c > ()(())((()))(())() ()( )( )( )() () ( ) () ()  ### Explanation The general idea is to use convolution to analyze pairs of consecutive symbols. There are four possible pairs: • ((: the second symbol should be on a lower line than the first • )): the second symbol should be on a higher line than the first • () or )(: the second symbol should be on the same line as the first When analyzing each pair, the line of the first symbol is already known, and the analysis tells the line of the second. Then the nex pair is analyzed, obtained by advancing one symbol, that is, with overlapping. j % input string 32 % ASCII code of space character - % subtraction. Will give 8 or 9 for '(' and ')' t8= % 1 for '(' symbols, 0 for ')' 2*1- % convert into 1 / -1 TTo % array [1 1] (for convolution) 3X5 % 'valid' flag for convolution 3$          % specify three inputs for convolution
X+          % convolution
ZS          % sign function
Ys          % cumulative sum
0wh         % prepend a 0
1+          % add 1. This gives line number of each symbol
wtn:w       % Vector [1 2 ... n] where n is string length. Rearrange
Z?          % create (sparse) matrix with three inputs: row, col, val
32+c        % add space code and convert to chat


# Charcoal, 12 bytes

ＦＳ¿⁼(ι↘(«Ｍ↑)


Try it online!

### Explanation

ＦＳ             For each character in next input as string
¿⁼(ι         If character is "("
↘(       Print "(" down and to the right - this is equivalent to printing "(" and moving down
«Ｍ↑)  Else move up and print ")"


# JavaScript (Node.js), 71 bytes

x=>[...x].map((_,n,s)=>s.map(c=>(c=='('?n--:++n)?' ':c).join).join



Try it online!

# JavaScript (Node.js), 85 bytes, just enough lines

x=>[...x].map((_,n,s)=>(Q=s.map(c=>(c=='('?n--:++n)?' ':c).join)<1?'':Q+
).join


Try it online!

• Invalid, "You may optionally print a single trailing newline." Apr 26 '18 at 4:53

f(y:b)|a<-sum[1|y=='(']=a:map(+(2*a-1))(f b)
f[]=[]
p s=[[last$' ':[a|b==i]|(b,a)<-zip(f s)s]|i<-[1..maximum$f s]]


Try it online!

# VIM, 101 bytes

↵ = Enter

qwlmto<esc>t@wq@w:s/()/(*)/g↵:set ve=all↵:set nows:↵set nosol↵qqvi)ygvr jPk/(↵@qq@qjjdGqeGl?*↵<C-V>ggoGr|@eq@e:%s/|//↵


# Retina, 65 bytes

./\S/{*\$$((?<-2>(\()*$$)*)\)
($.1* ) $$((?<-2>(\()*$$)*)\)$1


Try it online! Note: Trailing space. Link includes test cases. Explanation:

.


Don't print the spaces left over at the end.

/\S/{


Repeat until there are only spaces left.

*\


Print the result of this substitution without changing the current value.

$$((?<-2>(\()*$$)*)\)
($.1* )  Match pairs of balanced parentheses and replace their content with a run of spaces of the same length. $$((?<-2>(\()*$$)*)\)$1


Match balanced parentheses and replace the outer pairs with spaces.

For Retina 0.8.2 you have the choice of this 60 byte code:

{*$$((?<-2>(\()*$$)*)\)
($.1$* )
$$((?<-2>(\()*$$)*)\)
$1  Try it online! Note: Trailing space. Link includes test cases. Explanation: The differences are as follows: • Retina 0.8.2 doesn't have a while loop, only a convergence loop. However, this ends up printing blank lines while waiting for the loop to converge. • Retina 0.8.2 uses * for much the same effect as .*\. • Retina 0.8.2 uses $* instead of * in the replacement.

Alternatively, if the blank lines are a problem, you can use this 92 byte code:

{.+&¶$& $$((?<-2>(\()*$$)*)\)(?=.*¶.*$)
($.1$* )
$$((?<-2>(\()*$$)*)\)(?=.*$)$1
¶ +$ Try it online! Link includes test cases. Explanation: {  Repeat until the value converges. .+$
$&¶$&


Duplicate the last line.

$$((?<-2>(\()*$$)*)\)(?=.*¶.*$) ($.1$* )  Match pairs of balanced parentheses on what used to be the last line and replace their content with a run of spaces of the same length. $$((?<-2>(\()*$$)*)\)(?=.*$)
$1  Match pairs of balanced parentheses on the last line and replace the outer pairs with spaces. ¶ +$



Delete the last line if it's only spaces. This allows the loop to terminate.

# C, 949997 96

i,j,k,l;f(char*s){for(l=0;!i--;l-=puts(""))for(j=0;k=s[j++];putchar((k&1?--l:l++)?32:k))i&=l<2;}


Pure C version that doesn't use the consoles escape codes. Ungolfed:

i,j,k,l;                 // stop,iterator,current char,level
f(char*s){
for(l=0;               // reset level
!i--;              // stop ? return : stop = 1;
l-=puts(""))      // new line + next level
for(j=0;
k=s[j++];        // for each char
putchar(
(k&1?--l:l++)  // char == 41 ? prev level : next level
?32:k))        // only print brackets at level 0
i&=l<2;            // if level > 1 then don't stop
}


Try it online!

Changelog:

• +5 Byte Temporary fix to match rules
• -2 Byte Switch !i++ to !i-- drops the need to reset i
• -1 Byte Switch puts(""),--l to l-=puts("") Thanks to @ceilingcat
• I'm unable to find the relevant meta-post, but I'm pretty sure functions should be self-contained when run multiple times. So I think you should add i=j=k=l=0 to your code instead of resetting them in your main-method. I'll see if I can find the meta-post to explain it more clearly though, but I've had other people make these kind of comments on my answers in the past.. Nice answer nonetheless, so +1 from me. Apr 26 '18 at 8:31
• @KevinCruijssen Here it is Edit: mwahahaha
– Jo King
Apr 26 '18 at 8:34
• Found the meta-post, and here another relevant one. EDIT: @JoKing You beat me to it by 10 sec. ;) Apr 26 '18 at 8:34
• @KevinCruijssen A damn you're right what a sad day. Temp fix it at the cost of 5 byte. Hopefully I can get rid of some of them again. Ideas ? ;) Apr 26 '18 at 8:49
• @Christoph Unfortunately I don't see anything to golf (although there might of course be). I'm not too skilled in C to be completely honest. It seems already pretty well-golfed to me, hence the upvote I gave. ;) Apr 26 '18 at 8:55

# Jelly, 15 bytes

OḂ-*Ä+ƲṬ€z0ao⁶Y


Try it online!

Went through quite a few 16-byters before arriving at this...

O                  Codepoints
Ḃ                 mod 2. ('(' -> 0, ')' -> 1)
Ä              Cumulative sums of
-*               -1 to the power of each,
+Ʋ            plus the corresponding original residues.
Ṭ€          For each, an array with 1 at that index and 0 elsewhere.
z0        Zip filling with zeroes,
a       replace ones with corresponding elements of the input string,
o⁶     replace zeroes with spaces,
Y    join on newlines.


# K (ngn/k), 29 bytes

{+(|/i)$(-i:m-+\m-~m:2!x)$'x}


Try it online!

• (...)$'x left-pad each character of the input by the corresponding number of spaces • m:2!x take the input string mod 2 and store in m; translates "(" into 0 and ")" into 1 • m-~m convert 0s to -1s (leaving 1s as-is) • i:m-+\ calculate the "depth" of each character, storing in i • -i negate to left-pad (positive numbers will right-pad) • +(|/i)$ right-pad each string with spaces to the same length, then transpose the result

# Japt-Rx, 17 bytes

¬£®¥'(?Y´:°Y ?S:Z


Try it online!

### Unpacked & How it works

Uq mXYZ{UmZ{Z=='(?Y--:++Y ?S:Z

Uq      Convert the input string into array of chars
mXYZ{   Map with the function...
Here, Y (index) is used as the desired level of "telescoping"
UmZ{      Map on the original input string with the function...
Z=='(?      If this char is "("...
Y--:          Decrement Y
++Y           Otherwise, increment Y
?           If Y is nonzero (i.e. this char is *not* at desired level)...
S:            Replace with a space
Z             Otherwise, use the char as-is

Flags:
-R      Join the resulting array with newline
-x      Trim the resulting string on both ends


Ported from @l4m2's JS solution. It actually fits into Japt's built-ins quite nicely, and trailing whitespaces can be conveniently removed with the use of -x flag.

# Vyxalj, 27 bytes

ƛC∷&-¥n꘍nC₂&+;:vLG£ƛ¥↲;ÞTv∑


Try it Online!

A mess that I'm proud of. Thanks to lyxal for fixing a bug.

f s=fst\$span(any(>' '))[do