From: Shashank Date <ADATE@...>
Date: 2002-06-07T02:33:04+09:00
Subject: 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