perl - 如何将数组元素数组(不同长度)转换为树/哈希

Question

如何以编程方式转换这样的数组列表

$dat_a = [qw( a1 b1 c1 d1 e1)]
$dat_b = [qw( a1 b1 c2 d2 e1)]
$dat_c = [qw( a1 b2 c3)]
[...]

进入层次结构(散列)，如

# {a1}--{b1}-{c1}-{d1}{e1}=42
#     \     \{c2}-{d2}{e1}=84
#      |{b2}-{c3}=72

像这样用动态生成的代码填充散列:

$dat_hierarchy->{a1}{b1}{c1}{d1}{e1} ++
$dat_hierarchy->{a1}{b1}{c2}{d2}{e1} ++
$dat_hierarchy->{a1}{b2}{c3} ++

我的问题是运行中的数组有不同的 长度，并且最大长度在运行之间也是可变的。

类似的问题是将文件路径转换为目录树， 所以我假设会有一些标准算法来解决 这个问题。

如果我硬编码深度(或数组长度)，一个可能的解决方案是我 能想到的，就是把这个问题转化为更通用的一个 将矩阵转换为层次结构。这意味着转换数组 到矩阵(添加尾随 0 使所有数组具有相同的 长度)。这样解决方案就很简单了(如果脚本是 深度/长度硬编码)

#[Perlish pseudocode]
$max_array_idx        = find_maximum_array_index (\@list_of_arrays)
@lst_of_matrix_arrays = fill_to_same_length(\@list_of_arrays, $max_array_idx)
$hierarchy            = create_tree(\@list_of_matrix_arrays, $max_array_idx)

sub create_tree {
    my ($list_of_matrix_arrays, $max_array_idx) = @_;

    # <problem> how to dinamically handle $max_array_idx??

    # if I use fixed depth then is trivial
    # $max_fixed_idx = 2 
    # hardcoded hash construction for depth 3!

    # Trivial solution for fixed hash depth:
    foreach my $array ($list_of_matrix_arrays) {
        $dat_hierarchy->{$array->[0]}{$array->[1]}{$array->[2]} ++      
    }
}

所以，如果有任何关于如何避免硬编码的建议，我将不胜感激 哈希创建中使用的数组索引的最大数量，

一个可能的解决方案是使用一些元编程来使用运行时 $max_fixed_idx? 填充散列。 会不会像下面这样的好主意？

sub populate_hash {
    my ($array) = @_;
    my $array_max_idx =  @$array - 1;

    # create hash_string " $dat_hierarchy->{$array->[0]}{$array->[1]}{$array->[2]} ++"
    my $str = '$dat_hierarchy->';
    foreach my $idx (0..$array_max_idx) {
        # using the indexes instead the elements to avoid quotation problems
        $str .= '{$array->['.$idx.']}';
        # how to sanitize the array element to avoid code injection in the further eval? what happen if an array element is called "sub {system('rm -rf ~/')}" ;-)
        # http://xkcd.com/327/
    }
    $str .= ' ++';

    # populate hash
    # $str for lengh 3 arrays would be '$dat_hierarchy->{$array->[0]}{$array->[1]}{$array->[2]} ++'
    eval($str) or die 'error creating the hash';
}

递归呢？

Answer 1

我会使用类似 Tree::DAG_Node 的东西.

use Tree::DAG_Node;
my $root = Tree::DAG_Node->new();

my $data = [qw( a1 b1 c1 d1 e1)];

my $node = $root;
for my $item (@$data) {
    my $daughter = Tree::DAG_Node->new();
    $daughter->name($item);
    $node->add_daughter($daughter);
    $node = $daughter;
}