# Background

LISP programmers have taken over the world! Parentheses have been declared as sacred characters, and from now on, they can only be used in LISP programs. It has been decided that parentheses in literary works shall be replaced by footnotes, and it's your job to automate this for simplified Markdown text.

# Input

Your input is a single string containing alphabetic ASCII characters, spaces, and the special characters ,.!?(). It will not contain newlines or digits. The parentheses will be correctly matched.

# Output

You shall convert each matched pair of parentheses in the input string into a footnote. This happens as follows:

1. Replace the first matching pair of parentheses and the substring between them by a running number that starts from 1, wrapped between the Markdown tags <sup> and </sup>.
2. Append to the end of the string
• two newlines,
• the Markdown tag <sub>,
• the number from step 1,
• a space,
• the substring between the parentheses, and
• the closing tag </sub>, in this order.
3. If there are still parentheses left in the string, go to step 1.

Your output is the resulting string, possibly with a trailing newline. You don't have to implement this exact algorithm, as long as your output is correct. Note that there may be nested parentheses; in that case, we'll have footnotes that contain references to other footnotes. The substring between parentheses may also be empty. See the test cases below for examples.

# Rules and Scoring

Your can write either a full program or a function. The lowest byte count wins, and standard loopholes are disallowed.

If your language does not natively support decimal numbers (cough Retina cough), you may give the footnote numbers in another base, including binary or unary; however, using unary numbers imposes a penalty of +20%.

# Test Cases

Input:

This input contains no parentheses.

Output:

This input contains no parentheses.

Input:

This has (some) parentheses (but not so many).

Output:

This has <sup>1</sup> parentheses <sup>2</sup>.

<sub>1 some</sub>

<sub>2 but not so many</sub>

Input:

This has (nested (deeply (or highly?) nested)) parentheses (and several groups).

Output:

This has <sup>1</sup> parentheses <sup>2</sup>.

<sub>1 nested <sup>3</sup></sub>

<sub>2 and several groups</sub>

<sub>3 deeply <sup>4</sup> nested</sub>

<sub>4 or highly?</sub>

Input:

Hmm()(()(,))  a()((trt)(v( (((((wut)))))(X)(Y)(Z) )!?!?!?!))oooooooo(oooo)oooo

Output:

Hmm<sup>1</sup><sup>2</sup>  a<sup>3</sup><sup>4</sup>oooooooo<sup>5</sup>oooo

<sub>1 </sub>

<sub>2 <sup>6</sup><sup>7</sup></sub>

<sub>3 </sub>

<sub>4 <sup>8</sup><sup>9</sup></sub>

<sub>5 oooo</sub>

<sub>6 </sub>

<sub>7 ,</sub>

<sub>8 trt</sub>

<sub>9 v<sup>10</sup>!?!?!?!</sub>

<sub>10  <sup>11</sup><sup>12</sup><sup>13</sup><sup>14</sup> </sub>

<sub>11 <sup>15</sup></sub>

<sub>12 X</sub>

<sub>13 Y</sub>

<sub>14 Z</sub>

<sub>15 <sup>16</sup></sub>

<sub>16 <sup>17</sup></sub>

<sub>17 <sup>18</sup></sub>

<sub>18 wut</sub>

Note the empty lines between the footnotes.

• Can my program contain parentheses even if it's not written in Lisp or is that a punishable offence now? Sep 15 '15 at 19:06
• @MartinBüttner Parentheses in non-LISP programs are grudgingly permitted, as long as they're used for the greater good, like converting other parentheses into footnotes. Sep 15 '15 at 19:09
• Can the input be multiple lines? In that case, should footnotes be placed after each line, or at the end? E.g., what is the output for foo (bar)\nfoot (note)? Sep 16 '15 at 7:32
• @xebtl The input is always a single line. See section Input: "It will not contain newlines or digits." Sep 16 '15 at 12:34
• :( @ this spec numbering footnotes breadth-first instead of depth-first Sep 16 '15 at 19:11

# Emacs Lisp, 335 bytes

Foreword. This answer and the Scheme ones are currently the only answers officially sanctioned by both the Mighty Popular Republic of LISP and the Church of Emacs. Other answers, shorter or not, are considered a threat to peace. In particular, and with a profound disdain to any libelious allegation of McCarthyism that is sporadically heard from hostile opponents of the state, we enjoin anyone who has information about the real identity of the anonymous authors writing Nonlisp answers to contact your Local Bureau. It is reminded that everyone should take time to reflect and upvote in accordance to what he or she deeply believes will not threaten his or her future interactions with official representants of the power in place. Code is data. Data is code.

(defun p()(let(b(cpt 0)n)(goto-char 0)(while(search-forward"("()t)(setf b(point)n(number-to-string(incf cpt)))(backward-char)(forward-sexp)(backward-char)(kill-region b(point))(delete-backward-char 1)(delete-forward-char 1)(insert "<sup>"n"</sup>")(save-excursion(end-of-buffer)(newline 2)(insert "<sub>"n" ")(yank)(insert"</sub>")))))

More elegantly:

(defun parens ()
(let (b(cpt 0)n)
(goto-char 0)
(while(search-forward"("()t)
(setf b(point)n(number-to-string(incf cpt)))
(backward-char)
(forward-sexp)
(backward-char)
(kill-region b(point))
(delete-backward-char 1)
(delete-forward-char 1)
(insert "<sup>"n"</sup>")
(save-excursion
(end-of-buffer)
(newline 2)
(insert "<sub>"n" ")
(yank)
(insert "</sub>")))))

# Perl, 8175 72 bytes

71 bytes code + 1 byte command line argument.

Requires Perl 5.10 or newer (for recursive regex support)

The substitution string then simply pieces everything together based on the capturing groups. The footnote number is incremented by prepending a 1 to the last number with 1$5. • Retina is on a winning streak! – orlp Sep 15 '15 at 21:03 • @orlp Or is it? ;) Balancing groups are no match for recursive regex. That and not being able to handle decimal numbers... Sep 15 '15 at 23:00 • Time to steal the PHP wrapper and implement Retina around PCRE: Sep 16 '15 at 8:19 • @n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Normally, I'd rather have balancing groups than recursion, but there are some cases where the latter is more concise. Maybe one day I'll reimplement the .NET regex flavour for Retina and patch in some additional features. ;) Sep 16 '15 at 9:22 # Sacred JavaScript, 1510 bytes Fellow rebels, do not give in to their tyrannical demolition of the parenthesis! You must persevere! From the start, programming has been a free enterprise. Now, it has become a pervaded show of piety. We must show nothing less then absolute fearsomeness. Therefore, I have fought back! ( )( ((( (( )( ) (( ))( )) (( ( (( ) ( ()( ) (( ) )(( ((( ()((( ) ( ) )(( ) (((((( )( (())(( ) ) )( ()(( ((()((() ( ( ( ( )) (( )( ) (( ) )(((( ( () ) )( ( ()(( )( () ((( )(( ) )( ()((( ) ( ) ( )() (((( () ) (((( () ) ((() ) () ( ( ( ( )) ( )( ((((( )) (( )( ) (( ) )(((( ) ) ()( ((() ( ()(( ) ( ) )(( ))((( (( ) (( ) ( ()(( )( ) () ( ( ( ( ()( ) )( ()( ) () ( ( ( ( )( (( ( (( ) ((((( )) ) )(( )) (( )( ) (( ) )(((( ) ()( )) ) ) (( )( () ((( ( ) )(( )( )(((( ))( )() ) ()( )) (()( (()( ((()((() ( ( ( ( ( )) ( )( (((((( )(( ( (( )) ( (( ) )( ) )( ( )( ((() ( )( ((() ( ()( ()( () ) )( ()(( ) () ( ( ( ( ( )) ( )( (((((( )(( ( (( )) ( (( ) )( ) )( ( )( (((( ( )( ((() ( ()( ()( (()( ) )( ()(( ) () ( ( ( ( ( )) ( )( (((( ( ) ( ()( ((() ( ()( ())(( ) ( ) )( ()(( ))) ) () ( ( ( ((()) ( ( ( ((( ( ) )((( )( () ((( )((( ( )) ( ) ( ) ) ((((( )) (( )( ) (( ) )(((( (())( )) (()( ()(( ((() ( ( ( ( )( ) )(((( ( () ((( ) ( ) )(( (((( ( ()(( ) ( ) ) (((( () )( ((( ((((((()( ((() (( () )( )(( (()) ( )( ( )( ((() ) () ( ( ( (( ) ( ) )(( ))((( (( ) (( ) ( ()( ) (( ) )(( ((( ()((( ) ( ) )(( ) (((((( )( () ((( ) ( ) )(( (((( ( ()(( ) ( ) ) ((((((( ( (()) ( )( ) ) (( )(((( ( ()) ) )) ( )( (()((( ) (()( ( )( ) ) () )(( )(((( ( ()) ) )) ( )( ((() (()( ( )( ( ( ( ( ) ) (( )(((( ( ()) ) )) ( )( (()((( ) (()( ( )( ( () ( )( (()(( )( (()( ( )( ) ) () )(( )(((( ( ()) ) )) ( )( (())(( ) (()( ()(( ((() ) () ( (((()) No rules against using the sacred characters in a non-Lisp language. Nope, not at all. (In a little less compact way:) ( )( ((( (( )( ) (( ))( )) (( ( (( ) ( ()( ) (( ) )(( ((( ()((( ) ( ) )(( ) (((((( )( (())(( ) ) )( ()(( ((()((() ( ( ( ( )) (( ) ( ) (( ) )(((( ( () ) )( ( ()(( )( () ((( )(( ) )( ()((( ) ( ) ( )() (((( () ) (((( () ) ((() ) () ( ( ( ( )) ( )( ((((( )) (( )( ) ( ( ) )(((( ) ) ()( ((() ( ()(( ) ( ) )(( ))((( (( ) (( ) ( ()(( )( ) () ( ( ( ( ()( ) )( ()( ) () ( ( ( ( )( (( ( (( ) ((((( )) ) )(( )) (( )( ) (( ) )(((( ) ()( )) ) ) (( )( () ((( ( ) )(( ) ( )(((( ))( )() ) ()( )) (()( (()( ((()((() ( ( ( ( ( )) ( )( (((((( )(( ( (( )) ( (( ) )( ) )( ( )( ((() ( )( ((() ( ()( ()( () ) )( ()(( ) () ( ( ( ( ( )) ( )( (((((( )(( ( (( )) ( (( ) )( ) )( ( )( (((( ( )( ((() ( ()( ()( (()( ) )( ()(( ) () ( ( ( ( ( )) ( )( (((( ( ) ( ()( ((() ( ()( ())(( ) ( ) )( ()(( ))) ) () ( ( ( ((()) ( ( ( ((( ( ) )((( )( () ((( )((( ( )) ( ) ( ) ) (((( ( )) (( )( ) (( ) )(((( (())( )) (()( ()(( ((() ( ( ( ( )( ) )( ((( ( () ((( ) ( ) )(( (((( ( ()(( ) ( ) ) (((( () )( ((( ((((((()( ((() (( () )( )(( (()) ( )( ( )( ((() ) () ( ( ( (( ) ( ) )(( )) ((( (( ) (( ) ( ()( ) (( ) )(( ((( ()((( ) ( ) )(( ) (((((( )( () ( (( ) ( ) )(( (((( ( ()(( ) ( ) ) ((((((( ( (()) ( )( ) ) (( )(((( ( ()) ) )) ( )( (()((( ) (()( ( )( ) ) () )(( )(((( ( ()) ) )) ( )( ((() (()( ( )( ( ( ( ( ) ) (( )(((( ( ()) ) )) ( )( (()((( ) (()( ( )( ( () ( )( (()(( )( (()( ( )( ) ) () )(( )(((( ( ()) ) )) ( )( (())(( ) (()( ()(( ((() ) () ( (((()) This compiles to the expanded JavaScript in my other answer. This is a joke submission. # Lua, 222216204 201 bytes Golfed: s=io.read()g="%b()"c=1k=string l=k.find t=k.sub o=k.format a,b=l(s,g)while a do s=t(s,0,a-1)..o("<sup>%d</sup>",c)..t(s,b+1,#s).."\n\n"..o("<sub>%d %s</sub>",c,t(s,a+1,b-1))c=c+1 a,b=l(s,g)end print(s) Ungolfed: input=io.read() inputFormat="<sup>%d</sup>" footnoteFormat="<sub>%d %s</sub>" counter=1 a,b=string.find(input,"%b()") while a do current=string.sub(input,a+1,b-1) input=input.."\n\n"..string.format(footnoteFormat, counter, current) input=string.sub(input,0,a-1)..string.format(inputFormat, counter)..string.sub(input,b+1,#input) counter=counter+1 a,b=string.find(input,"%b()") end print(input) • wouldn't a repeat a,b=l(s,g) ... untill a<1 loop be shorter than your while? Feb 9 '16 at 13:59 # Scheme, 92 bytes Frustrated with implementing the breadth-first search in Real Lisp,1 the powers-that-be decide to take a more pragmatic approach. After all, Parentheses are sacred, but brackets are not.2 (lambda(s)(list->string(map(lambda(c)(case c((#$$)#$)((#$$)#$)(else c)))(string->list s))) 1. listen not to those heretics from the so-called “church” of Emacs! 2. They are not Racket programmers, are they? • Scheme shall be called Schism: saying it is the "Real Lisp" is the actual heresy. And you say it is pragmatic? This hack of an answer shows the true nature of schemers ;-) Sep 17 '15 at 9:39 • @coredump And you would claim your monstrously non-functional elisp answer is an instance of True Lisp? It may take a little longer, true, but when the Scheme answer is finished, it will be The Right Thing! Sep 17 '15 at 10:32 # Haskell, 210 bytes n#x|b==""=a|1<2=a++"<sup>"++m++"</sup>"++((n+1)#(c++"\n\n<sub>"++m++' ':init d++"</sub>"))where m=show n;(a,b)=span(/='(')x;(d,c)=[x|x@(y,_)<-map(splitAt(tail b))[0..],'('!y<')'!y]!!0;c!l=[1|m<-l,m==c] p=(1#) Usage example: *Main> putStrLn$ p "This has (nested (deeply (or highly?) nested)) parentheses (and several groups)."
This has <sup>1</sup> parentheses <sup>2</sup>.

<sub>1 nested <sup>3</sup></sub>

<sub>2 and several groups</sub>

<sub>3 deeply <sup>4</sup> nested</sub>

<sub>4 or highly?</sub>

How it works:

n # x                      -- # does all the work, n is the current number of the
--   footnote and x the input string
| b=="" = a              -- if b (see below) is empty, there's no ( in the
--   string and the result is 'a' (see below)
| 1<2   = a++"<sup>"++m++"</sup>"++ ((n+1)#(c++"\n\n<sub>"++m++' ':init d++"</sub>"))
-- otherwise (b not empty) build the output string
--   starting with 'a' and a footnote number and a
--   recursive call with the current footnote appended
--   to the rest of the string

where
m = show n;              -- turn n into string
(a,b) = span (/='(') x;  -- split the input string x into two parts:
--   a: everything before the first (
--   b: beginning with the first ( to the end
--   if there's no (, a is x and b is empty
(d,c) = [x|x@(y,_)<-map(splitAt(tail b))[0..],'('!y<')'!y]!!0;
-- find matching ) in the tail of b ('tail' to remove leading '(')
--   d: everything before and including the matching )
--   c: everything behind the matching )
c!l=[1|m<-l,m==c]        -- helper function that builds a list of 1s for every character searched for
--   we have reached the matching ) if the list for ( is
--   shorter (less than, <) the list for )

# Scheme, 533 bytes

With indentation:

(letrec ((l string->list)
(n number->string)
(? null?)
(p (lambda (o) (or (pair? o)(? o))))
(a car)
(d cdr)
(e append)
(i 0)
(x
(lambda (h t)
(if (? h)
t
(case (a h)
((#$$) (let ((s (x (d h) ()))) (x (a s) (e t (d s))))) ((#$$) (cons (d h) (list t)))
(else
(x (d h) (e t (list (a h)))))))))
(f
(lambda (h t F)
(cond ((? h)
(let ((w (e t F)))
(if (find p w) (f w()()) w)))
((p(a h))
(set! i(+ 1 i))
(f (d h)
(e t (e (l "<sup>")
(l (n i))
(l "</sup>")))
(e F (e (l "\n\n<sub>")
(l (n i))
'(#\ )
(a h)
(l "</sub>")))))
(else (f (d h)
(e t (list (a h)))
F))))))
(print (list->string (f (x (l (read-line))
())
()
()))))

Yes, this is 533 bytes when all the optional whitespace is removed. Bask in the functional glory.

I implemented more or less the algorithm in the description: x groups the input by parentheses and f replaces the first level of groups by footnotes, repeating until no more groups are left. I am sure it can be made shorter, but I do not see how it could be made much shorter without switching to a different algorithm.

As written, it is a complete program. You can try it out here, but because repl.it apparently cannot deal with (read-line) you have to put the input string in its place. A completely ungolfed version is here.

EDIT: As pointed out in the comments, I changed the parentheses () into brackets [] in the repl.it versions. This was purely for convenience during programming and debugging. The version as posted now works with ().

• +1, but I don't understand why you change square brackets. If I change #\[ '#] by the respective parenthesis (and update tests), this works without problem. Is there a reason you left the square ones? is it related to your previous answer? Sep 17 '15 at 15:49
• @coredump you are absolutely right. I changed to brackets because (a) paren character literals messed up repl.it's paren matching and (b) in debugging, output (which will include a lot of parens from lists) was much more readable with brackets. Then I just left it that way. I will edit. Sep 17 '15 at 15:54

# JavaScript ES6, 244 bytes

Serious answer (only works on FireFox, to my knowledge)

d=(s,n=1)=>{u=s.search(/$$/);if(index<a=0)return s;for(i=index;i<s.length;i++){if(s[i]==")")a-=1;if(s[i]=="(")a+=1;if(!a)break}return d(s.replace(v=s.slice(index,i+1),"<sub>"+n+"</sub>")+ <sub>+n+" "+v.replace(/^\(|$$$/g,"")+"</sub>",n+1)} Expanded: function deparen(s,n=1){ index = s.search(/$$/); if(index<0) return s; a=0; for(i=index;i<s.length;i++){ if(s[i]==")") a-=1; if(s[i]=="(") a+=1; if(!a) break; } v=s.slice(index,i+1) f=v.replace(/^\(|$$$/g,"");
return deparen(s.replace(v,"<sub>"+n+"</sub>")+"\n\n<sub>"+n+" "+f+"</sub>",n+1);
}