Beefy Boxes and Bandwidth Generously Provided by pair Networks
Think about Loose Coupling
 
PerlMonks  

Re: Walking a boolean tree to produce matching inputs

by japhy (Canon)
on Sep 18, 2014 at 02:29 UTC ( #1100988=note: print w/replies, xml ) Need Help??


in reply to Walking a boolean tree to produce matching inputs

I have finally solved this problem, after months of cheating and using File::Glob to do the hard work for me. (I ran into string-length limitations with File::Glob which prevented it from working for very long boolean statements.)

Here is my Perl solution, translated from (obligatory shudder) PHP. Hopefully the code speaks for itself and is not in need of much documentation for explaining its logic. NOTE: "not" nodes are skipped, because the point of this function is to come up with lists of terms that will match the logic.

#!/usr/bin/perl -l use strict; use warnings; my $tree = ['and', ['or', 1, 2], ['not', 3], ['or', 4, 5, 6]]; my $opts = options($tree); for my $o (@$opts) { print "OPTION: ", join(", ", @$o); } sub options { my ($tree, $opts) = @_; if (! $opts) { $opts = [ [] ]; options($tree, $opts); return $opts; } else { my $op = $tree->[0]; if ($op eq 'and') { for my $val (@$tree[1 .. $#$tree]) { if (ref($val) eq 'ARRAY' and ($val->[0] eq 'and' or $val->[0] +eq 'or' or $val->[0] eq 'not')) { my $subtree = options($val); my @new; for my $branch (@$subtree) { for my $o (@$opts) { push @new, [ @$o, @$branch ]; } } @$opts = @new; } else { for my $o (@$opts) { push @$o, $val; } } } } elsif ($op eq 'or') { my @new; for my $val (@$tree[1 .. $#$tree]) { if (ref($val) eq 'ARRAY' and ($val->[0] eq 'and' or $val->[0] +eq 'or' or $val->[0] eq 'not')) { my $subtree = options($val); for my $branch (@$subtree) { for my $o (@$opts) { push @new, [@$o, @$branch]; } } } else { for my $o (@$opts) { push @new, [@$o, $val]; } } } @$opts = @new; } } }
Jeffrey Pinyan (Perl, PHP ugh, JavaScript) — @PrayingTheMass
Melius servire volo
Catholic Liturgy

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1100988]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (8)
As of 2020-06-01 13:51 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?