# Length of String Using Set Theory

From Wikipedia Set-theoretic definition of natural numbers

The set N of natural numbers is defined as the smallest set containing 0 and closed under the successor function S defined by S(n) = n ∪ {n}.

The first few numbers defined this way are 0 = {}, 1 = {0} = {{}}, 2 = {0,1} = {{},{{}}}, 3 = {0,1,2} = {{},{{}},{{},{{}}}}.

Using this definition of natural numbers count the length of a string.

Input a string of characters from a-zA-Z of any length

Output the length of the string in set notation without separators

Examples

Input Empty string

Output {}

Input a

Output {{}}

Input aaaa

Output {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}

For readability output for 'aaaa' with separators is

{
{}
{{}}
{{} {{}} }
{{}   {{}}   {{} {{} } }   }
}


Conditions

1. No digits 0 to 9 to appear in the code;
2. No use of character code conversion to generate numbers;
3. No use of +-*/ for arithmetic calculations including increment and decrement;
4. No mathematical operations other than Boolean Logic;
5. Input string does not count in determining byte length;

Winner Shortest code length in bytes.

As this is my first question I hope I have made it clear and rigorous enough. Friendly advice accepted.

• Hm, can you implement a recursive definition without calling f(n-1)? – Martin Ender Apr 10 '14 at 10:27
• I have a solution (non-optimal in terms of byte length) that does not use recursion. If A is an array then A.pop();f(A) is recursive. – jing3142 Apr 10 '14 at 10:34
• That's a good point. – Martin Ender Apr 10 '14 at 10:37
• @jing3142 Kudos for implementing a solution yourself to make sure it's possible. +1 for great question. – Kyle Strand Apr 10 '14 at 18:49
• What does the restriction to a-zA-Z mean? Should we detect whitespace/rubish? or should we just expect this and report the length of the string, regardles on the content? – V-X Apr 11 '14 at 8:44

## GolfScript (18 17 bytes)

'{'\{;.'}'++}/'}'


Takes input on the stack (so if run as a program, via stdin). Leaves the output as two strings on the stack (so if run as a program, the correct output is sent to stdout).

To leave a single string on the stack, either append + to concat, or use the alternative

'{}'\{;.);\'}'++}/


### Dissection

# Stack: input-str
'{'\
# Stack: <0< input-str  where <0< means the string representing 0 without its final }
# Loop over each character of the input string
{
# Stack: <n< char
;
# Concatenate two copies of <n< and a }
.'}'++
}/
# Push the final } to the stack
'}'


Alternative:

# Stack: input-str
'{}'\
# Stack: <0> input-str  (where <0> means the string representing 0)
# Loop over each character of the input string
{
# Stack: <n> char
;
# Duplicate <n> and remove the final '}'
.);
# Stack manipulations
\'}'
# Stack: <n>-less-final-'}' <n> '}'
# Concatenate the three strings to get <n+1>
++
}/


### Impact of the restrictions

If decrement were allowed, it would permit the 15-byte solution

'{}'\{;..,(/*}/


# Haskell function, 35 34 characters

f[]="{}";f(_:x)='{':f x++tail(f x)


 f[]="{}";f(_:x)='{':f x++tail(f x);main=print$f"aaaa"  (47 characters if you don't mind extra quotes around the output; if you do, use putStr instead of print for a total of 48 characters) # Haskell program, 51 50 characters f[]="{}";f(_:x)='{':f x++tail(f x);main=interact f  • If you're OK with reversing the order, since it's a set, you can use: f[]="{}";f(_:x)='{':f x++(tail.f)x to save a character. – isaacg Apr 10 '14 at 11:12 • @isaacg Nice one. OP should tell us if he minds, though. – John Dvorak Apr 10 '14 at 12:13 • As its a set order does not matter so @isaacg 's suggestion is good – jing3142 Apr 10 '14 at 12:40 # Python 3 - 64 o=['{}'] for a in input():o+=['{'+''.join(o)+'}'] print(o.pop())  If inlining the input is allowed: # Python 2 - 54 o=['{}'] for a in'whatever':o+=['{'+''.join(o)+'}'] print o.pop()  • Isn't raw-input() the method of inputing not the input string itself. Not being familiar with the range of languages possible I was disallowing the string length if something like w='aaaaaaaaaaaa' was necessary within the code. Sorry if not clear. Any help in re-wording question accepted. – jing3142 Apr 10 '14 at 10:52 • I see. I'll rewrite my code accordingly. In general, however, I think you should just leave that line out. Essentially every language has an I/O system. – isaacg Apr 10 '14 at 10:55 • You can save a symbol by using o[-1] instead of o.pop() – aland Apr 11 '14 at 11:06 • "No digits 0 to 9 to appear in the code;" – isaacg Apr 11 '14 at 18:06 • A strange character-save for the first one: Initialize o=[], which becomes o=['{}'] after one step, and lengthen the input by one by replacing it with '_'+input(), cutting the space after in. – xnor Jul 18 '14 at 13:41 # Javascript 70 (chars) s='';c=prompt().split('');while(c.pop()){s+='{'+s+'}'}alert('{'+s+'}')  This was my effort before setting the question. I would assume someone with more knowledge of Javascript than me can probably beat it. Thank you Jan Dvorak and Peter Taylor for further reductions # now 62 s='{';c=prompt().split('');while(c.pop())s+=s+'}';alert(s+'}')  # and now 61 s='{';for(c=prompt().split('');c.pop();)s+=s+'}';alert(s+'}')  Explanation of Original Code set s to be empty input string into c and split into an array while it is possible to pop() a character from c do so and reset s=s{s} as successor output current s but need to surround with set brackets. • You don't need braces after while (saves one character). – John Dvorak Apr 10 '14 at 13:00 • There's a 7-char saving without any more knowledge of JS required: initialise s='{' and ditch the two '{'+. (This then behaves like my GS solution). There's a further 1-char saving by using for instead of while and pulling in one of the two initialisations to the for-loop initialisation. – Peter Taylor Apr 10 '14 at 13:00 • @peter-taylor not sure how you mean to apply for-loop. I have only ever used it for counting. – jing3142 Apr 10 '14 at 16:00 • for(a;b;c){d} is directly equivalent to a;while(b){d;c} in most languages which have both. So while for(;b;) is identical to while(b) in effect and character count, for(a;b;) saves one char over a;while(b) and is identical in effect. – Peter Taylor Apr 10 '14 at 16:26 • @peter-taylor +1 for very clear and concise explanation within a comment – jing3142 Apr 10 '14 at 17:21 # J - 22 20 char '{','}' '{'&(,,~)~#  How this can be derived:  #'123' NB. string length 3 'Left' (,,~) 'Right' NB. dyad to concat L,R,R LeftRightRight '{' (,,~) '}' NB. using braces {}} '{'&(,,~) '}' NB. bind left argument, now it's a monad {}} '{'&(,,~) '{'&(,,~) '}' NB. twice {{}}{}} '{'&(,,~)^:2 '}' NB. ^: is monad functional power {{}}{}} '{'&(,,~)^:3 '}' NB. any integer {{{}}{}}{{}}{}} 3 '{'&(,,~) '}' NB. convenient feature of dyadic & {{{}}{}}{{}}{}} '}' '{'&(,,~)~ 3 NB. swap argument order {{{}}{}}{{}}{}} '}' '{'&(,,~)~ #'123' NB. using string length {{{}}{}}{{}}{}} '{', '}' '{'&(,,~)~ #'123' NB. add final brace {{{{}}{}}{{}}{}} ('{','}' '{'&(,,~)~#) '123' NB. works as a verb {{{{}}{}}{{}}{}}  Alternatively, this can be written '{','{'&(,,~)&'}'@#, meaning the same thing. Usage:  '{','}' '{'&(,,~)~# 'aaaa' {{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}} f =: '{','}' '{'&(,,~)~# NB. can be assigned to a function f 'VeryBig' {{{{{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}{{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}{{{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}{{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}{{{{}}{}}{{}}{}}{{{}}{}}{{}}{}}  Haskell - 35 charactes g[]="{}";g(_:x)=(init.g)x++g x++"}"  Solution is influenced by Jan Dvorak's one, but without reversing the order. # Scala, 64 characters def f(s:String):String=s"{${s.tails.toSeq.tail.map(f)mkString}}"


Note the dual roles that both the braces and s play in this code.

EDIT: removed a digit

• There is a digit in the code – jing3142 Apr 10 '14 at 15:48
• @jing3142 Oops. Not any more. – Karol S Apr 10 '14 at 18:02

# Python 3 (44)

s='{'
for _ in input():s+=s+'}'
print(s+'}')


At each step, s is the string representing the set with the final } removed. We create the set representing n+1 from the set representing n via the relationship f(n+1) = f(n) ∪ {f(n)}. To implement the union with strings, we append the string for {f(n)}, which is exactly s but with the final } returned, and neglect to include the final } in the result. Finally, we add back a final '}' before printing.

If I may hardcode the string, the character count cuts down to 35 character, switching to Python 2 to save parantheses on the print.

s='{'
for _ in'string':s+=s+'}'
print s+'}'


There might be a way to save the space after the print by doing something like print'{'+s with a reversed s, but this messes up with the += appending on the right.

# gs2, 12 bytes

7b 7d 05 27 a0 42 30 30 e4 43 2e 32


mnemonics:

"{}"
right-uncons @0 swap + + b5
rot length times


# Mathematica, 115 characters

StringReplace[ToString@Function[s,NestWhile[#~Append~#&,{},(s~Read~Character//StringQ)&]]@StringToStream@"test",", "->""]


The complete code as shown has 121 characters, but 6 of them are used for the input string ("test") which, according to the rules, doesn't count.

Without the requirement that there are no delimiters, the code length could be reduced further by 24 characters; without explicit conversion to string then another 9 characters could be removed.

• I thought that removing the need for deliminators, which are usually are required in set notation, I was helping to reduce code size. So if using them reduces your code size go ahead and use them. – jing3142 Apr 11 '14 at 7:45

# Ruby, 27, kind of cheating

a=*a
gets.chars{a=*a,a}
p a


Questionable things:

1. Output looks like [[], [[]], [[], [[]]], [[], [[]], [[], [[]]]]]
2. Most methods of input to ruby will include a trailing newline, which inflates the count by 1.
• It should be perfectly legit if you inspect the array manually and tr the result. – John Dvorak Apr 15 '14 at 18:08

# Pure Bash, 54

f()([ $@ ]&&(a=f${@%?}
echo $a{$a}))
echo {f $@}  Output: $ ./strlenset.sh
{}
$./strlenset.sh a {{}}$ ./strlenset.sh aa
{{}{{}}}
$./strlenset.sh aaa {{}{{}}{{}{{}}}}$ ./strlenset.sh aaaa
{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}
$ # Julia 43 f(z)="{"foldl((x,y)->"$x{$x}","",{z...})"}"  The construct {z...} expands the string z into an array. Fold loops over all elements of the array ignoring the contents and instead building up from the empty string. The function foldl is available in Julia 0.30. Sample Output julia> f("") "{}" julia> f("aa") "{{}{{}}}" julia> f("aaaa") "{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}" julia> f("aaaaaa") "{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}"  # Haskell, 31 bytes foldl(\s _->init s++s++"}")"{}"  # Mathematica, 4557 48 bytes "{"~~Fold[#~~"{"~~#~~"}"&,"",Characters@#]~~"}"&  A 36 bytes solution: Fold[{##{##}}&@@#&,{},Characters@#]&  However, it uses some arithmetic calculations. # Delphi XE3 (264) Ok I dont even come close to the other but it was fun to do :) Probably overthinking it. Going to see if there is a better way to do this. ### Golfed uses System.SysUtils;var s,f:string;a:TArray<char>;b:TArray<string>;i,x:integer;begin readln(s);a:=s.ToCharArray;f:='{';setlength(b,Length(a));for I:=Low(a)to High(a) do begin s:='{';for x:=Low(b)to High(b)do s:=s+b[x];b[i]:=s+'}';f:=f+b[i];end;writeln(f+'}');end.  ### Ungolfed uses System.SysUtils; var s,f:string; a:TArray<char>; b:TArray<string>; i,x:integer; begin readln(s); a:=s.ToCharArray; f:='{'; setlength(b,Length(a)); for I:=Low(a)to High(a) do begin s:='{'; for x:=Low(b)to High(b)do s:=s+b[x]; b[i]:=s+'}'; f:=f+b[i]; end; writeln(f+'}'); end.  ### Testing results Tested strings with length 0..10 {} {{} } {{} {{}} } {{} {{}} {{}{{}}} } {{} {{}} {{}{{}}} {{}{{}}{{}{{}}}} } {{} {{}} {{}{{}}} {{}{{}}{{}{{}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}} } {{} {{}} {{}{{}}} {{}{{}}{{}{{}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}} } {{} {{}} {{}{{}}} {{}{{}}{{}{{}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}} } {{} {{}} {{}{{}}} {{}{{}}{{}{{}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}} } {{} {{}} {{}{{}}} {{}{{}}{{}{{}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}}} } {{} {{}} {{}{{}}} {{}{{}}{{}{{}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}}} {{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}{{}{{}}{{}{{}}}{{}{{}}{{}{{}}}}}}}}}} }  • Thanks for trying. In my mind I was considering length as a mathematical operation as it returns a number and as is the use of a 'for' loop which involves counting. – jing3142 Apr 10 '14 at 12:37 Perl 5: 33 characters It's not quite clear which characters I should count as part of the solution. Probably not the echo ... | part because that's just used to feed a line in to stdin. Probably not the name of the perl binary, because you could rename that whatever you wanted. So I've counted the command-line switches passed to perl, the quote marks wrapped around the Perl code, and the Perl code itself. # 1 2 3 # 12 3456789012345678901234567890123$ echo "aaaa" | perl -ple'$s.="{$s}"while s/.//;$_="{$s}"'


Also, related.

• You should count pl as astandard, but you get -e and the quotes around the code for free. Ref – Peter Taylor Apr 10 '14 at 14:53

# Perl 6: 37 characters

say ({"\{@_.join()\}"}...*)["(input string)".chars]


or from STDIN:

say ({"\{@_.join()\}"}...*)[get.chars]


{"\{@_.join()\}"}...* makes a lazy list of the set forms of the natural numbers, and we just grab the one we need with get.chars.

The lazy list might be more readably written:

-> *@prev { '{'~ @prev.join ~'}' } ... *


Which reads pretty similarly to the definition.

## Dart: 85 characters

a(p,i)=>(--i).isNegative?p:a("$p{$p}",i);
main(s){print("{\${a("",s.first.length)}}");}


The requirement of not using "0" really bites, otherwise .first would be [0] and (..).isNegative would be ..<0.

# Pyth, 13 bytes

+u++GG\}z\{\}


This is the golfed Pyth equivalent of @xnor's Python answer. Note that Pyth is newer than this question, so this answer is not eligible to win this challenge.

Demonstration.

# Javascript, 171149147 142 bytes

(Will likely be golfed further later)

n=prompt().split("");for(a=[];n.pop();)a.push(a.slice());alert(JSON.stringify({a:a})[R="replace"](/[^]/g,"")[R](/$/g,"{")[R](/$/g,"}"));