那些遇到过的问题

在Perl中创建树数据结构(必须是本机)以表示位于外部文件中的调用树

Pau*_*aul 3 algorithm perl hierarchical-trees data-structures perl-data-structures

这是该文件的一个示例.

  powrup.asm            POWER_UP
                  ......EXTERNAL_RAM_ADDRESSING_CHECK    powrup.asm:461
                  ......EXRAM    powrup.asm:490
                  ......INRAM    powrup.asm:540
                  ......OUTPUT_TEST    powrup.asm:573
                  ............AD_READ    douttst.asm:276
                  ............AD_READ    douttst.asm:366
                  ......OUTPUT2_TEST    powrup.asm:584
                  ............AD_READ    douttst2.asm:253
                  ............AD_READ    douttst2.asm:342
                  ......OUTPUT3_TEST    powrup.asm:599
                  ............AD_READ    douttst3.asm:307
                  ............AD_READ    douttst3.asm:398
                  ......INPUT_TEST    powrup.asm:614
                  ......PROGRAM_PINS2_INPUT    powrup.asm:629
                  ......ARINC_TEST    powrup.asm:633
                  ............ARINC_LEVEL_TEST    artest.asm:178
                  ..................AD_READ    arltst.asm:204
                  ..................AD_READ    arltst.asm:250
                  ..................AD_READ    arltst.asm:300
                  ..................AD_READ    arltst.asm:346
                  ..................AD_READ    arltst.asm:396
                  ..................AD_READ    arltst.asm:442
                  ............ARINC_READ    artest.asm:209
                  ............ARINC_WORD_TXRX_TEST    artest.asm:221
                  ..................ARINC_OUT    artxrx.asm:207
                  ..................ARINC_READ    artxrx.asm:221
                  ............ARINC_READ    artest.asm:251
                  ............ARINC_WORD_TXRX_TEST    artest.asm:263
                  ..................ARINC_OUT    artxrx.asm:207
                  ..................ARINC_READ    artxrx.asm:221
                  ......PROGRAM_PINS2_INPUT    powrup.asm:640
                  ......PROGRAM_PIN_TEST    powrup.asm:642
                  ......PT_RCVR_BITE    powrup.asm:645
                  ............AD_READ10    ptbite.asm:225
                  ..................AD_READ    adread10.asm:141
                  ............AD_READ10    ptbite.asm:308
                  ..................AD_READ    adread10.asm:141
                  ............AD_READ10    ptbite.asm:384
                  ..................AD_READ    adread10.asm:141
                  ............AD_READ10    ptbite.asm:467
                  ..................AD_READ    adread10.asm:141
                  ............AD_READ10    ptbite.asm:542
                  ..................AD_READ    adread10.asm:141
                  ............AD_READ10    ptbite.asm:622
                  ..................AD_READ    adread10.asm:141
                  ......PROGRAM_PINS2_INPUT    powrup.asm:653
                  ......EXEC_INIT    powrup.asm:663
Run Code Online (Sandbox Code Playgroud)

...表示呼叫深度.该行后面的文件名表示文件名和父项中调用的行号.我可以解析文件.解析文件后,我尝试做的是将数据放入n-ary树中.我正在进行数据耦合和控制耦合分析,并且已经收集了构建中所有变量的所有设置/使用数据.我现在需要能够遍历树并根据深度计算出在使用情况之前是否有任何设置或任何设置但未使用的情况.我认为树遍历最有意义.

以下是收集数据的示例:

$hash_DB{'alt_deviation_evaluation.asm->ALT_STATUS'} = [
   'alt_deviation_evaluation.asm',
   'ALT_STATUS',
   '1.1',
   1,
   "",
   "",
   "135,188,202,242",
   "130,144"
];

'alt_deviation_evaluation.asm->ALT_STATUS' is the file name and variable name.

   'alt_deviation_evaluation.asm', File name
   'ALT_STATUS', Variable name
   '1.1',   versions of file
   1,       indicates has been processed
   "",     not used (maybe in future)
   "",     not used  (maybe in future)
   "135,188,202,242", variable Set line numbers for this fileVariable
   "130,144"          Variable Use line number for this file/Variable
Run Code Online (Sandbox Code Playgroud)

我还有一个包含所有变量名的数组.缩短的例子:

our @vars_list = (
  'A429_TX_BUFFER_LENGTH',
  'A429_TX_INPUT_BUFFER',
  'A429_TX_INT_MASK',
  'ABS_ALT_DIFF',
  'ACTUAL_ALT',
  'ADDRESS_FAIL',
  'AD_CONV_FAIL',
  'AD_CONV_SIGNAL',
  'AD_DATA',
  'AD_FAIL',
  'AD_STATUS',
  'AIR_MODE',
  'AIR_MODE_COUNT',
  'AIR_MODE_LAST',
  'ALPHA_COR_SSM',
  'ALPHA_EC_SSM',
  'ALPHA_GRAD_SSM',
  'ALPHA_LE_SSM',
  'ALPHA_LG_SSM',
  'ALPHA_MAX_MC_SSM'
};
Run Code Online (Sandbox Code Playgroud)

我最大的障碍是找出适当的数据结构和算法来完成这项任务.

我认为深度优先搜索n-ary树会给我想要的东西.

这是我的最终解决方案:

#!/usr/local/bin/perl
# !/usr/bin/perl
use Data::Dumper; #!!!
sub Create_Tree;
sub Treverse;

#for my $node (@TREE) {
#   print_node($node[0], 1);
#}


#Main

our @TREE;
Create_Tree("call_tree.small_01.txt");
my $str = Dumper @TREE;
$str =~ s/^(\s+)/' 'x(length($1)>>2)/meg;
#print "\n\n=======================================\n$str"; #!!!
#print "\n\n=======================================\n" . (Dumper @TREE); #!!!

#print "Arr = @TREE, SZ = $#TREE\n\n";
Treverse(\@TREE,1);

sub Create_Tree
{
  my ($call_tree) = @_;
  my @stack;
  my ($old_depth, $p_arr) = (0, \@TREE);

  open(IN, "< $call_tree" ) or die "Can not open '$call_tree' for input.\n";
  for (<IN>)
  {
    if (m/^(\s*)(\S+)\s*=>\s*(\S+):(\d+)/ or m/^(\s*)(\S+)()()/)
    {
      my ($depth, $callee_fn, $caller_fn, $ln, $diff) = ($1, $2, $3, $4, 0);
      $depth = int(length($depth) / 6);
      $diff  = $depth - $old_depth;

      if ($diff == 1)
      {
        push @stack, $p_arr;
        $p_arr = \@{$$p_arr[$#{$p_arr}]{children}};
      }
      elsif ($diff < 0)
      {
        $p_arr = pop @stack while ++$diff <= 0;
      }
      elsif ($diff > 1)
      {
        die "Incorrectly formated call tree:\n  $_\n";
      }

      push @$p_arr, {
          caller    => $caller_fn,
          called_by => $callee_fn,
          at_line   => $ln
      };

      $old_depth = $depth;
    }
  }

  close IN;
}
exit;
Run Code Online (Sandbox Code Playgroud)

OUTPUT看起来像这样:

......file1

    ............file1    101:A
    ..................XXX.AA    102:AA
    ........................XXX.AAA    103:AAA
    ........................XXX.AAB    104:AAB
    ..............................XXX.AABA    105:AABA
    ..................XXX.AB    106:AB
    ........................XXX.ABA    107:ABA
    ............file1    108:B
    ..................XXX.BA    109:BA
    ........................XXX.BAA    110:BAA
    ........................XXX.BAB    111:BAB
Run Code Online (Sandbox Code Playgroud)

从这个call_tree.txt文件:

file1
      A => file1:101
            AA => XXX.AA:102
                  AAA => XXX.AAA:103
                  AAB => XXX.AAB:104
                        AABA => XXX.AABA:105
            AB => XXX.AB:106
                  ABA => XXX.ABA:107
      B => file1:108
            BA => XXX.BA:109
                  BAA => XXX.BAA:110
                  BAB => XXX.BAB:111
Run Code Online (Sandbox Code Playgroud)

使用这个子程序:

sub Treverse
{
  my ($p_arr, $level) = @_; 
  for (my $ind=0; $ind<=$#{$p_arr}; $ind++)
  {

        print "." x ($level*6);
        if ($$p_arr[$ind]{'caller'} ne "") {print "$$p_arr[$ind]{'caller'}" . " " x 4;}
        if ($$p_arr[$ind]{'at_line'} ne "") {print "$$p_arr[$ind]{'at_line' }" . ":";}
        if ($$p_arr[$ind]{'called_by'} ne "") {print "$$p_arr[$ind]{'called_by'}" . "\n";}


    Treverse(\@{$$p_arr[$ind]{children}}, $level +1) if defined $$p_arr[$ind]{children};

  }
}
# END of Treverse
Run Code Online (Sandbox Code Playgroud)

bvr*_*bvr 6

以下是如何使用Wes的答案打印您构建的结构.

处理完数据后,您最终会得到以下结果:

my @nodes = (
    {   name => 'ARINC_TEST', file => 'powrup.asm', line => 633,
        children => [
            {   name => 'ARINC_LEVEL_TEST', file => 'artest.asm', line => 178,
                children => [
                    { name => 'AD_READ', file => 'arltst.asm', line => 204 },
                    { name => 'AD_READ', file => 'arltst.asm', line => 250 },
                    { name => 'AD_READ', file => 'arltst.asm', line => 300 },
                    { name => 'AD_READ', file => 'arltst.asm', line => 346 },
                    { name => 'AD_READ', file => 'arltst.asm', line => 396 },
                    { name => 'AD_READ', file => 'arltst.asm', line => 442 },
                ],
            },
            {   name => 'ARINC_READ', file => 'artest.asm', line => 209,
                children => [],
            },
            {   name => 'ARINC_WORD_TXRX_TEST', file => 'artest.asm', line => 221,
                children => [
                    { name => 'ARINC_OUT',  file => 'artxrx.asm', line => 207 },
                    { name => 'ARINC_READ', file => 'artxrx.asm', line => 221 },
                ],
            }
        ]
    }
);
Run Code Online (Sandbox Code Playgroud)

该结构是递归的,并且children关键指向另一个散列的arrayref.要打印出来,您需要递归代码:

for my $node (@nodes) {
    print_node($node, 1);
}

sub print_node {
    my ($node, $level) = @_;

    # the node itself
    print "." x ($level*6)
        , $node->{name}, " " x 4
        , $node->{file}, ":"
        , $node->{line}, "\n";

    # recurse for children
    if(defined $node->{children}) {
        for my $child (@{ $node->{children} }) {
            print_node($child, $level + 1);
        }
    }
}
Run Code Online (Sandbox Code Playgroud)

对于上面的数据,代码输出 

......ARINC_TEST    powrup.asm:633
............ARINC_LEVEL_TEST    artest.asm:178
..................AD_READ    arltst.asm:204
..................AD_READ    arltst.asm:250
..................AD_READ    arltst.asm:300
..................AD_READ    arltst.asm:346
..................AD_READ    arltst.asm:396
..................AD_READ    arltst.asm:442
............ARINC_READ    artest.asm:209
............ARINC_WORD_TXRX_TEST    artest.asm:221
..................ARINC_OUT    artxrx.asm:207
..................ARINC_READ    artxrx.asm:221
Run Code Online (Sandbox Code Playgroud)

归档时间：

查看次数：

6021 次

最近记录：

14 年，8 月 前
相关归档
与STO检测统一 38
什么是Youtube评论系统排序算法？ 20
最小化Matlab中数组列的总和 16
高级横幅旋转算法 11
重命名列表项 9
扭转链表 7
最后剩余的号码 7
HashMap:使用公共密钥添加值并将其打印出来 4
用 Haskell 表示计算图 3
如何实现连通房？ 2
难疑归档
在JavaScript中深度克隆对象的最有效方法是什么？ 5181
Bash中的Echo newline打印文字\n 2171
在vi中快速缩进多行 2111
如何将列表拆分为大小均匀的块？ 2068
如何调试Node.js应用程序？ 1531
将浮点数限制为两个小数点 1527
如何解决"断点当前不会被命中.此文档没有加载任何符号." 警告？ 1456
如何在Python中追加文件？ 1446
如何配置git在本地忽略某些文件？ 1237
如何查看仅一个用户提交的git日志？ 1178