algorithm - Perl 两列平面文件到复杂的无序列表树

Question

我有一个从我们的 AD 结构中提取的组织结构图的数据文件，看起来像这样，经理是第一个字段，员工是第二个字段 - 在某些情况下，经理会照顾一些员工:

__EXAMPLE__
user4   user8
user8   user9
    user1
user1   user2
user2   user3
user2   user5
user2   user4
user3   user5
user4   user6
user4   user7

这需要在 HTML 无序列表中输出，如下所示:

# Intended output
#
# <ul>
#   <li>user1</li>
#   <ul>
#       <li>user2</li>
#       <ul>
#           <li>user3</li>
#           <ul>
#               <li>user5</li>
#           </ul>
#           <li>user4</li>
#           <ul>
#               <li>user6</li>
#               <li>user7</li>
#               <li>user8</li>
#             <ul>
#               <li>user9</li>
#             </ul>
#           </ul>
#       </ul>   
#   </ul>
# </ul>

我想我可以在这个位置使用示例代码:Parse Text file and create complex tree structure in perl但我正在努力将初始示例转换为所需的格式。

我有一些代码将整个数据文件吸入一个数组，检查管理器值不为空，然后递归地尝试匹配树上的下一个管理器(直到它达到空值)，这应该给我输出喜欢:

user1
user1 user2
user1 user2 user3
user1 user2 user3 user5
user1 user2 user4
user1 user2 user4 user6
user1 user2 user4 user7
user1 user2 user4 user8
user1 user2 user4 user8 user9

不幸的是，我的 Perl 生锈了，我的代码看起来很糟糕；我不确定我是否以最好的方式处理这个问题，所以希望能从比我更聪明的人那里得到一些智慧的话。

当前示例:

#!/usr/bin/perl
#
use strict;
use warnings;

my @Complete = <DATA>;

foreach my $line (@Complete) {
    chomp($line);
    my ($fl, $usr) = split(/\t/, $line); #Formal Leader && User
    foreach my $leader (@Complete) {
        chomp($leader);
        if ($leader =~ /$fl$/) {
            $line = $leader."\t".$usr;
            ($fl,$usr) = split(/\t/, $line, 2);
            $leader = '';
        }
        last if ($fl eq '');
    }
    print "'".$line."'\n";
}

__DATA__
user4   user8
user8   user9
    user1
user1   user2
user2   user3
user2   user5
user2   user4
user3   user5
user4   user6
user4   user7

Answer 1

下面的程序很接近你想要的:

use strict;
use warnings;

use HTML::Entities;

sub render {
    my ($underlings_of, $level, $key) = @_;
    my $underlings = $underlings_of->{$key} or return;
    print "  " x $level, "<ul>\n";
    for my $underling (sort @$underlings) {
        print "  " x ($level + 1), "<li>", encode_entities($underling), "</li>\n";
        render($underlings_of, $level + 1, $underling);
    }
    print "  " x $level, "</ul>\n";
}

my %underlings_of;

while (my $line = readline DATA) {
    chomp $line;
    my ($mgr, $emp) = split /\t/, $line;
    push @{$underlings_of{$mgr}}, $emp;
}

render(\%underlings_of, 0, '');

__DATA__
user4   user8
user8   user9
    user1
user1   user2
user2   user3
user2   user5
user2   user4
user3   user5
user4   user6
user4   user7

它产生以下输出:

<ul>
  <li>user1</li>
  <ul>
    <li>user2</li>
    <ul>
      <li>user3</li>
      <ul>
        <li>user5</li>
      </ul>
      <li>user4</li>
      <ul>
        <li>user6</li>
        <li>user7</li>
        <li>user8</li>
        <ul>
          <li>user9</li>
        </ul>
      </ul>
      <li>user5</li>
    </ul>
  </ul>
</ul>

用户 user5 被列出两次，因为它们在输入层次结构中出现了两次，在 user2 下和 user3 下。这意味着您的结构实际上并不是一棵树，而是一个有向无环(希望如此)图。

对于其他方法，https://en.wikipedia.org/wiki/Topological_sorting可能会有帮助，因为我相信您的问题是拓扑排序的一个实例。