in reply to Parsing Boolean expressions

Just for fun :)

no guarantees whatsoever...

use strict;
use warnings;

my @equations;

while(<DATA>){
  chomp;
  next unless $_;               # ignore empty
  next if $_ =~ /^\s*#/;        # ignore comment
  s/(\w+)/\$$1/g;               # variables

  # ops by decending precedence
  s/'/^1/g;                     # negation by xor 1
  s/\*/ and /g;                 # and
  s/\+/ or /g;                  # or
  s/=(.*)$/= ( $1 )/;           # assignment after ( RHS )

  push @equations,"$_;\n";
}

my $format = "%s | %s %s %s %s\n";
$\="\n";
#print @equations;


for my $eq (@equations) {
  print "\n $eq";
  printf  $format, qw/Y A B C D/;
  for my $A (0,1) {
    for my $B (0,1) {
      for my $C (0,1) {
        for my $D (0,1) {
          my $Y=undef;
          eval $eq;
          printf $format, $Y, $A, $B, $C, $D; 
        }
      }
    }
  }
}
__DATA__
#Y=A+B'
#Y=A*B'
#Y=A'
#Y=A*B
#Y=A+B

Y = A + (B*C)
Y = A + (B' + (C*D)')
Y = A*(B*(C'+D)')

[download]

 $Y = (  $A  or  ($B and $C) );

Y | A B C D
0 | 0 0 0 0
0 | 0 0 0 1
0 | 0 0 1 0
0 | 0 0 1 1
0 | 0 1 0 0
0 | 0 1 0 1
1 | 0 1 1 0
1 | 0 1 1 1
1 | 1 0 0 0
1 | 1 0 0 1
1 | 1 0 1 0
1 | 1 0 1 1
1 | 1 1 0 0
1 | 1 1 0 1
1 | 1 1 1 0
1 | 1 1 1 1

 $Y = (  $A  or  ($B^1  or  ($C and $D)^1) );

Y | A B C D
1 | 0 0 0 0
1 | 0 0 0 1
1 | 0 0 1 0
1 | 0 0 1 1
1 | 0 1 0 0
1 | 0 1 0 1
1 | 0 1 1 0
0 | 0 1 1 1
1 | 1 0 0 0
1 | 1 0 0 1
1 | 1 0 1 0
1 | 1 0 1 1
1 | 1 1 0 0
1 | 1 1 0 1
1 | 1 1 1 0
1 | 1 1 1 1

 $Y = (  $A and ($B and ($C^1 or $D)^1) );

Y | A B C D
0 | 0 0 0 0
0 | 0 0 0 1
0 | 0 0 1 0
0 | 0 0 1 1
0 | 0 1 0 0
0 | 0 1 0 1
0 | 0 1 1 0
0 | 0 1 1 1
0 | 1 0 0 0
0 | 1 0 0 1
0 | 1 0 1 0
0 | 1 0 1 1
0 | 1 1 0 0
0 | 1 1 0 1
1 | 1 1 1 0
0 | 1 1 1 1

[download]

Cheers Rolf
(addicted to the Perl Programming Language and ☆☆☆☆ :)
Je suis Charlie!

update

  • wait there is a precedence problem ... = before and
  • Solved

    • Replies are listed 'Best First'.
    Re^2: Parsing Boolean expressions (hack)
    by Anonymous Monk on Apr 23, 2017 at 15:40 UTC
      Nice. You can almost parse the expression with the same technique. 
      use strict;
use warnings;
use Data::Dump;
my @exprs = (
   "Y = A + (B*C)",
   "Y = A + (B' + (C*D)')",
   "Y = A*(B*(C'+D)')",
);
for my $expr (@exprs) {
   print "$expr\n";
   $expr =~ s/\(/[/g;
   $expr =~ s/\)/],/g;
   $expr =~ s/(\w+|[+*'=])/"$1",/g;
   my @parse = eval $expr;
   dd(\@parse);
   print "\n";
}
__END__
Y = A + (B*C)
["Y", "=", "A", "+", ["B", "*", "C"]]

Y = A + (B' + (C*D)')
["Y", "=", "A", "+", ["B", "'", "+", ["C", "*", "D"], "'"]]

Y = A*(B*(C'+D)')
["Y", "=", "A", "*", ["B", "*", ["C", "'", "+", "D"], "'"]]

      [download]
    		[reply]
    [d/l]
        > You can almost parse the expression with the same technique.

        not really, for a syntax tree you would need an [OP, arg1, arg2] format.

        this

        ["B", "'", "+", ["C", "*", "D"], "'"]]

        doesn't help without further parsing because precedence is still not resolved.

        Rather 

        [ "or", 
    [ "not" , "B" ] , 
    [ "not", 
        [ "and", "C", "D"]
    ] 
]

        [download]

        without recursive parsing hard to achieve, I just delegated the hard part to Perl, deliberately ignoring what the OP didn't tell us yet.

        edit

        For instance if the = is not an assignment but a condition, he would want solutions for this equation system...

        (which I could produce at least by brute force for small variable sets, if we had a guarantied format)

        Cheers Rolf
        (addicted to the Perl Programming Language and ☆☆☆☆ :)
        Je suis Charlie!

    		[reply]
    [d/l]
    [select]
          Yeah, that's why I said "almost." You need to postprocess it a bit to get a proper syntax tree.
    		[reply]

    In Section Seekers of Perl Wisdom