blob: caf24b15960453da90ba915fe4723a0d71bbfae3 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
|
#! /usr/bin/env raku
unit sub MAIN (Str $tree = '1 | 2 3 | 4 * 5 6 | * 7', :v($verbose), :g(:$graph));
class BinaryNode
{
has Numeric $.value is rw;
has BinaryNode $.left is rw;
has BinaryNode $.right is rw;
method id
{
self.Str ~~ /(\d+)/; return $0.Str;
}
method sum
{
my $sum = self.value;
$sum += self.left.sum if self.left.defined;
$sum += self.right.sum if self.right.defined;
return $sum;
}
}
my @btree = $tree.split("|")>>.words;
my @old-nodes;
my @new-nodes;
for @btree.reverse -> $row
{
my @current = @$row;
@old-nodes = @new-nodes;
@new-nodes = ();
for @current -> $value
{
if $value eq "*"
{
@new-nodes.push("*");
next;
}
my $left = @old-nodes.shift // "*"; $left = Nil if $left eq "*";
my $right = @old-nodes.shift // "*"; $right = Nil if $right eq "*";
@new-nodes.push(BinaryNode.new(value => $value.Int,
left => $left // Nil,
right => $right // Nil));
}
}
my $btree = @new-nodes[0];
say ": Sum: { $btree.sum }" if $verbose;
say ": { $btree.raku }\n" if $verbose;
traverse($btree);
say ": { $btree.raku }\n" if $verbose;
graph($btree) if $graph;
sub traverse ($current)
{
$current.value = $sum - $current.value;
traverse($current.left) if $current.left.defined;
traverse($current.right) if $current.right.defined;
}
sub graph ($graph)
{
say 'digraph foogrph {';
say ' node [shape = record,height=.1];';
do-it($graph);
say '}';
sub do-it ($current)
{
say " node{ $current.id }[label = \"<left> |<center> { $current.value }|<right> \"];";
if $current.left.defined
{
say " \"node{ $current.id }\":left -> \"node{ $current.left.id }\":center;";
do-it($current.left);
}
if $current.right.defined
{
say " \"node{ $current.id }\":right -> \"node{ $current.right.id }\":center;";
do-it($current.right);
}
}
}
|
