如何在Perl中通过引用传递树数据结构?

Question

我正在写一个脚本来解决非常基本的方程组。我将方程转换成二叉表达式树，分离出我想要的值的变量，然后进行替换。

这就是我遇到问题的地方，我有一个函数"替换"它遍历我要替换的方程左边的二叉表达式树。当我找到要替换的变量时，我用另一个方程的表达式树替换节点。

但是当我尝试返回新树时，我的替换不在那里。这显然是一个按引用/按值传递的问题，但我找不到解决它的方法。

下面是一个显示不工作的部分的脚本:

#!/usr/bin/perl
use strict;
use warnings;
use Data::Dumper;
sub inorder {
my $expression = shift;
my $node = $expression;
if ($node->{type} eq "operator") {
print "(";
inorder($node->{left});
print $node->{value};
inorder($node->{right});
print ")";
}
else {
print $node->{value};
}
}
sub substitution {
my ($inserted_equation, $master_equation) = @_;
my $inserted_expression = $inserted_equation->{right_side};
my $insertion_point     = $inserted_equation->{left_side}->{value};
my $master_expression   = $master_equation->{right_side};
my @stack_tree_walk;
my $node = $master_expression;
push @stack_tree_walk, {$node->%*, left_visited => 0, side=> "left"};
while(@stack_tree_walk) {
if ($node->{type} eq "variable" and $node->{value} eq $insertion_point) {
foreach (@stack_tree_walk) {

}
#           print $node->{value};
#           print Dumper $inserted_expression;
$node = $inserted_expression;       # WORKS
#           print Dumper $node;                 # WORKS
#           print Dumper $master_expression;    # DOES NOT WORK
pop @stack_tree_walk;
$node = $stack_tree_walk[-1];
}
elsif ($node->{type} eq "operator") {
if (not $stack_tree_walk[-1]->{left_visited}) {
$stack_tree_walk[-1]->{left_visited} = 1;
$node = $node->{left};
push @stack_tree_walk, {$node->%*, left_visited => 0, side=> "left"};
}
elsif ($node->{side} eq "left") {
$node = $node->{right};
$stack_tree_walk[-1]->{side} = "right";
push @stack_tree_walk, {$node->%*, left_visited => 0, side=> "left"};
}
else {
pop @stack_tree_walk;
$node = $stack_tree_walk[-1];
}
}
else {
pop @stack_tree_walk;
$node = $stack_tree_walk[-1];
}
}
return {right_side=>$master_expression, left_side=>$master_equation->{left_side}};
}

my $equation = {left_side => { type=> "variable",
value=> "y"},
right_side=> { type=> "operator",
value=> "*",
left=> {type=> "variable", value=> "a"},
right=> {type=> "variable", value=> "b"} }
};
my $insertion = {left_side => { type=> "variable" ,
value=> "a" },
right_side=> { type=> "operator",
value=> "+",
left=> {type=> "variable", value=> "x"},
right=> {type=> "variable", value=> "y"} }
};
$,="";
$="";
print "equations before substitutionn";
inorder($equation->{left_side});
print "=";
inorder($equation->{right_side});
print "n";
inorder($insertion->{left_side});
print "=";
inorder($insertion->{right_side});
print "n";
print "------------------n";
$,="n";
$="nn";
my $final = substitution($insertion, $equation);
$,="";
$="";
print "------------------n";
print "equation substitutedn";
inorder($final->{left_side});
print "=";
inorder($final->{right_side});
print "n";

输出:

equations before substitution
y=(a*b)
a=(x+y)
equation substituted
y=(a*b)                     <==== this is the ERROR
y=((x+y)*b)                 <==== this should be the RIGHT result

我希望有人能告诉我哪一部分是错的。谢谢你。

Answer 1

$node本质上是指向结构体的指针。您的代码只是将$node设置为不同的指针，即$inserted_expression。你不用这样改变结构，你只需要改变一个局部变量$node来指向不同的东西。基本上你可以这样做:

$struct = { foo => { bar => 1 } };
$node = $struct->{foo}; # points at { bar => 1 } in $struct
$node = { bar => 2 }  # points at { bar => 2 } and not longer into $struct
print(Dumper($struct)); # unchanged

如果你想改变struct中的值，你需要接受一个引用而不只是取值，即

$struct = { foo => { bar => 1 } };
$node = $struct->{foo}; # reference to value of { foo => ... }, currently { bar => 1 }
$$node = { bar => 2 }  # changes value of { foo => ... } to { bar => 2 }
print(Dumper($struct)); # changed