# Unflatten

This is probably a general programming question but I am using Ruby as my
lang of choice hence a post to this group.

I am trying to convert a flat list (array) of tokens into a nested list
(hence the name UNflatten) using a simple rule:
Every token which looks like ‘(’ begins a nested list and the corresponding
’)’ token ends it … in a recursive fashion.
e.g:
[“a”, “(”,“b”, “)”] ==> [“a”,[ “b” ]]
[ “(”, “a”, “(”,“b”, “)”, “)”] ==> [[“a”,[“b”]]]

Of course, I also want a function (reflatten) which traverses the nested
list to generate the original back.
My first attempt looks like this (see code below).

Any suggestions to improve will be highly appreciated.
Right now I don’t care as much for the efficiency as for the ecomony of
expression.
Thanks,
– Shanko

···

def reflatten(list,left = ‘(’, right = ‘)’,accu=[],level = 0)

``````print level,'<=' if \$DEBUG
p list, accu if \$DEBUG

return accu if not list

if list.length < 1
print '.1.' if \$DEBUG
accu  += [right] if level > 0
return accu
else
e = list[0]
if e.type == list.type
print '.2.' if \$DEBUG
accu = reflatten(e,left,right,accu + [left],level+1)
reflatten(list[1..-1],left,right,accu,level)
else
print '.3.' if \$DEBUG
reflatten(list[1..-1],left,right,accu+[e],level)
end
end
``````

end

def unflatten(list, left = ‘(’,right = ‘)’,accu = [], level = 0)
print level,’=>’ if \$DEBUG
p list,accu if \$DEBUG

``````return accu if list.length < 1

e = list[0]

if e == left
print '.1.'  if \$DEBUG
unflatten(list[1..-1],left,right,accu << [], level+1)
else
if e == right
if (level > 1) and (accu[-2].type == accu.type)
print '.2.' if \$DEBUG
unflatten(list[1..-1],left,right,accu[0..-3] << (accu[-2] <<
``````

accu[-1]),level-1)
else
print ‘.3.’ if \$DEBUG
unflatten(list[1…-1],left,right,accu,level-1)
end
else
if level > 0
print ‘.4.’ if \$DEBUG
unflatten(list[1…-1],left,right,accu[0…-2] << accu[-1] +
[e],level)
else
print ‘.5.’ if \$DEBUG
unflatten(list[1…-1],left,right,accu+[e],level)
end
end
end

end

if \$0 == FILE

``````s = "( ( ( a ( b ) ( ( c ) d ) ( e ) f ) ) )"
# s = "R ( b ( c ( ( a ( Z ) ) ( k ) ) d ) e ) ( a ( b ) ( c ( d ) ) e )
``````

U ( d e ) B ( f ) Y "
puts s

``````t = s.split
u = unflatten(t)
p u
puts

r = reflatten(u)
p r
puts

puts r.join(" ")
``````

end

Shashank Date wrote:

I am trying to convert a flat list (array) of tokens into a nested list
(hence the name UNflatten) using a simple rule:
Every token which looks like ‘(’ begins a nested list and the corresponding
‘)’ token ends it … in a recursive fashion.
e.g:
[“a”, “(”,“b”, “)”] ==> [“a”,[ “b” ]]
[ “(”, “a”, “(”,“b”, “)”, “)”] ==> [[“a”,[“b”]]]

Of course, I also want a function (reflatten) which traverses the nested
list to generate the original back.

Coincidentally, I wrote an inverse for flatten yesterday. (Well,
actually only a right inverse since flatten is not injective.) What you
are doing isn’t precisely an inverse of Array#flatten, though, which I
guess is why you have reflatten. So this may not be useful to you.

Anyway, it’s called Enumerable#nest. You give it a proc that calculates
the depth of each item, and it returns a nesting of arrays in which each
item has the desired depth. I’m using it to parse strings with
Python-like indentation syntax, but it isn’t limited to strings. It’s
calculate the depth from each object by itself–you have to know the
paren count.

Any suggestions appreciated…

···

module Enumerable
def nest(&compare)
ary = to_a
i = 0
# wrap into Array::Iterator?
items_left = proc { i < ary.size }
get_cur = proc { ary[i] }
go_next = proc { i += 1 }
Enumerable.nest items_left, get_cur, go_next, compare
end

def Enumerable.nest items_left, get_cur, go_next, compare
# should handle compare.arity == 2 like a <=> proc
result = ; item = depth = nil
while items_left
item = get_cur
depth = compare[item]
base_depth ||= depth

``````  if depth < base_depth
break
elsif depth > base_depth
result << nest(items_left, get_cur, go_next, compare)
else
result << item; go_next[]
end
end
return result
``````

end
end

str = <<END
a
aa
ab
aba
abb
abba
abbaa
abbb
ac
b
ba
bb
c
ca
END

lines = str.split “\n”
nested = lines.nest { |line| line.scan(/^\s*/)[0].length }
p nested
flat = nested.flatten
p flat
p flat == lines

[Shashank Date]:

I am trying to convert a flat list (array) of tokens into a nested list
(hence the name UNflatten) using a simple rule:
Every token which looks like ‘(’ begins a nested list and the corresponding
‘)’ token ends it … in a recursive fashion.
e.g:
[“a”, “(”,“b”, “)”] ==> [“a”,[ “b” ]]
[ “(”, “a”, “(”,“b”, “)”, “)”] ==> [[“a”,[“b”]]]

My suggestions:

def unflatten(list, left=‘(’, right=‘)’)
current =
stack =

``````list.each do |x|
if x == left
stack << (current << [])
current = current[-1]
elsif x == right
raise "unbalanced" if stack.size == 0
current = stack.pop
else
current << x
end
end
raise "unbalanced" unless stack.size == 0
return current
``````

end

def reflatten(list, left=‘(’, right=‘)’)
acc =
list.each do |x|
if Array === x
acc << left
acc += reflatten(x, left, right)
acc << right
else
acc << x
end
end
return acc
end

// Niklas

Hi,

“Niklas Frykholm” r2d2@acc.umu.se wrote in message
news:slrnafvnam.s4k.r2d2@shaka.acc.umu.se…

[Shashank Date]:

I am trying to convert a flat list (array) of tokens into a nested
list
(hence the name UNflatten) using a simple rule:
Every token which looks like ‘(’ begins a nested list and the
corresponding
‘)’ token ends it … in a recursive fashion.
e.g:
[“a”, “(”,“b”, “)”] ==> [“a”,[ “b” ]]
[ “(”, “a”, “(”,“b”, “)”, “)”] ==> [[“a”,[“b”]]]

My suggestions:

def unflatten(list, left=‘(’, right=‘)’)
current =
stack =

``````list.each do |x|
if x == left
stack << (current << [])
current = current[-1]
elsif x == right
raise "unbalanced" if stack.size == 0
current = stack.pop
else
current << x
end
end
raise "unbalanced" unless stack.size == 0
return current
``````

end

Simple but awful solution.

def unflatten(list)
eval list.inspect.gsub(/“(”,/ , ‘[’).gsub(/“)”/ , ‘]’)
end

Park Heesob.

Joel VanderWerf wrote:

module Enumerable
def nest(&compare)

FWIW, I just realized that a grouping can be done very easily using
#nest:

module Enumerable
def group(&test)
nest { |x| test ? 1 : 0 }
end
end

p [1, 2, “three”, “four”, 5, “six”].group { |x| x.is_a? String }

==> [1, 2, [“three”, “four”], 5, [“six”]]

Park Heesob wrote:

Simple but awful solution.

def unflatten(list)
eval list.inspect.gsub(/“(”,/ , ‘[’).gsub(/“)”/ , ‘]’)
end

Park Heesob.

Sometimes it may work, but it’s quite simple to construct more
complicated cases for which it fails.

E.g.:

list = [“"(”,“a”]
unflatten(list)

gives parse error.

Best regards, Christian

Excellent suggestions, Joel, I have added them my perosnal “goodies”
library.
And you are right, they do address a different but similar problem.

I am studying your solution and being a newbie it is taking me a while for
it to sink in ;-), but I am getting there.
Thanks again.

“Joel VanderWerf” vjoel@PATH.Berkeley.EDU wrote in message
news:3D013DB0.5811BD55@path.berkeley.edu…

···

Joel VanderWerf wrote:

module Enumerable
def nest(&compare)

FWIW, I just realized that a grouping can be done very easily using
#nest:

module Enumerable
def group(&test)
nest { |x| test ? 1 : 0 }
end
end

p [1, 2, “three”, “four”, 5, “six”].group { |x| x.is_a? String }

==> [1, 2, [“three”, “four”], 5, [“six”]]

Thanks. BTW, I’ll include #nest and #group in future versions of
“Enumerable Tools” on RAA.

Shashank Date wrote:

···

Excellent suggestions, Joel, I have added them my perosnal “goodies”
library.
And you are right, they do address a different but similar problem.

I am studying your solution and being a newbie it is taking me a while for
it to sink in ;-), but I am getting there.
Thanks again.

“Joel VanderWerf” vjoel@PATH.Berkeley.EDU wrote in message
news:3D013DB0.5811BD55@path.berkeley.edu…

Joel VanderWerf wrote:

module Enumerable
def nest(&compare)

FWIW, I just realized that a grouping can be done very easily using
#nest:

module Enumerable
def group(&test)
nest { |x| test ? 1 : 0 }
end
end

p [1, 2, “three”, “four”, 5, “six”].group { |x| x.is_a? String }

==> [1, 2, [“three”, “four”], 5, [“six”]]