Perl兩列平面文件到一個複雜的無序列表樹

Question

我有一個組織結構圖的數據文件，它已經從我們的AD結構中拉出來了，看起來像這樣，Manager是第一個字段，第二個是員工 - 在某些情況下，經理會看幾個工作人員後：

__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但我很努力g將最初的例子轉換爲所需的格式。

我已經有一些代碼將整個數據文件吸收到一個數組中，檢查管理器值是否爲空，然後遞歸地嘗試匹配樹上的下一個管理器（直到它命中null），這應該給我輸出如：

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和unde下r user3。這意味着你的結構並不是一棵樹，它是一個有向無環（有希望）的圖。

對於其他方法，https://en.wikipedia.org/wiki/Topological_sorting可能會有幫助，因爲我相信您的問題是拓撲排序的一個實例。