P is for Practical PerlMonks

Evaluate arbitrary boolean expressions

by gauss76 (Sexton)
 on Mar 13, 2018 at 10:02 UTC Need Help??
gauss76 has asked for the wisdom of the Perl Monks concerning the following question:

Hi All,

I would like to know if there exists any way to evaluate arbitray boolean expressions containing true and false values in perl.

For example I have a perl sub that will generate the result of a single if statement as T (True) or F (False). I can then combine the results from multiple calls to the aforementioned sub to create a more complex boolean expression such as (T && F) || (F && F) etc. I then need to evaluate this new expression to T or F using algebra logic. Does anything exist in perl to do this?

Please note that I have used the operators &&=logical AND, ||=Logical OR in my explanation above but others may be more appropriate.

Many thanks for any feedback on this.

gauss76

Replies are listed 'Best First'.
Re: Evaluate arbitrary boolean expressions
by Corion (Pope) on Mar 13, 2018 at 10:26 UTC

Do you want to do algebraic symbolic reduction of the terms or do you just want to evaluate it?

One approach would be to evaluate every atomic expression left-to-right until you have no more operators, and then using De Morgan's laws to resolve parentheses.

Thanks for the quick response.

In answer to your question: I am only interested in whether the expression I generate is true or false. I do not need to do any algebraic symbolic reduction of the terms.

A simplicistic approach would be to repeatedly apply these three rules to simplify things:

• replace F || X with X and T && Y with Y
• replace F && X with F and T || Y with T
• replace an atomar term within parenthes with that atomar term

```#!perl -w
use strict;
my @terms = (
'( ( T || F ) && T )',
'( ( T || F ) && ( F && F ))'
);

sub simplify {
my( \$term ) = @_;
\$term =~ s!\s+!!g; # eliminate all whitespace
my \$changed;
do {
\$changed = 0;
\$changed ||= (\$term =~ s!F\|\|!!g);
#print "\$term (\$changed)\n";
\$changed ||= (\$term =~ s!\|\|F!!g);
#print "\$term (\$changed)\n";
\$changed ||= (\$term =~ s!T\&\&!!g);
#print "\$term (\$changed)\n";
\$changed ||= (\$term =~ s!\&\&T!!g);
#print "\$term (\$changed)\n";
\$changed ||= (\$term =~ s!F\&\&!!g);
#print "\$term (\$changed)\n";
\$changed ||= (\$term =~ s!\&\&F!!g);
#print "\$term (\$changed)\n";
\$changed ||= (\$term =~ s!T\|\|!!g);
#print "\$term (\$changed)\n";
\$changed ||= (\$term =~ s!\|\|T!!g);
#print "\$term (\$changed)\n";

\$changed ||= (\$term =~ s!\(([FT])\)!\$1!g);
#print "\$term (\$changed)\n";
} while \$changed;
return \$term
}

for my \$t (@terms) {
print "\$t => " . simplify( \$t ), "\n";
};
Re: Evaluate arbitrary boolean expressions
by hippo (Canon) on Mar 13, 2018 at 10:53 UTC
I can then combine the results from multiple calls to the aforementioned sub to create a more complex boolean expression such as (T && F) || (F && F) etc.

If your sub is called foo() then it's simply

```my \$bool = (foo() && !foo()) || (!foo() && !foo());

Yes, sure, but my question is how can I evaluate your variable \$bool to true or false?

```if (\$bool) {
print "It's true\n";
}
else {
print "It's false\n";
}

...roboticus

When your only tool is a hammer, all problems look like your thumb.

Re: Evaluate arbitrary boolean expressions
by LanX (Bishop) on Mar 13, 2018 at 17:49 UTC
double negation !! will return the "normalized" boolean value in Perl
• !!0 is "the" False
• !!1 is "the" True

```D:\Users\RolfLangsdorf>perl -de0

Loading DB routines from perl5db.pl version 1.37
Editor support available.

Enter h or 'h h' for help, or 'perldoc perldebug' for more help.

main::(-e:1):   0

DB<1> x [!!0,!!1]
0  ARRAY(0x28d1a8)
0  ''
1  1

DB<2>

if you need more syntactic sugar, than map them with use constant or use Readonly

```  DB<1> use constant {TRUE => !!1, FALSE=> !!0}

DB<2> x [TRUE,FALSE]
0  ARRAY(0x4c6170)
0  1
1  ''

Cheers Rolf
(addicted to the Perl Programming Language and ☆☆☆☆ :)
Wikisyntax for the Monastery

Re: Evaluate arbitrary boolean expressions
by Eily (Prior) on Mar 13, 2018 at 13:44 UTC

It looks like you want something that is true or false when used in boolean context (meaning, && and || work as expected) and is the string "true" or "false" when used in string context. Do note that perl doesn't have a specific boolean type, but uses either strings or numbers instead. You can obtain what (I think) you want with an overloaded object. I got lazy so what I did is use the code of boolean and replaced the "overload" call with:

```use overload
'0+' => sub { \${\$_[0]} },
'""' => sub { \${\$_[0]} ? "true" : "false"},
'!' => sub { \${\$_[0]} ? \$false : \$true },
fallback => 1;
Then the return value of true and false can be used a string. There are some possible issues though, the string "false" is not empty, so it is actually true, and the string "true" turns into the number 0 so it will be different from the number you may get from true() (which is 1):
```use boolean;
\$\ = \$/;

my \$false = false;
print "\\$false is \$false" unless \$false;

my \$copy = \$false;
print '\$copy is also false' if not \$copy;

my \$str_false = "\$false";
print '\$str_false is true?' if \$str_false;
print 'But equal to false' if \$str_false eq \$false;

my \$true = true;
my \$str_true = "\$true";
print '\$str_true is true but != from true' if \$str_true and (\$str_true
+ != true);

print "The value of this test is: ", boolean(true||false);
```\$false is false
\$copy is also false
\$str_false is true?
But equal to false
\$str_true is true but != from true
The value of this test is: true
It kind of works as long as you do not try to convert the values to a string or a number, and then use them again as boolean. The best solution IMHO would rather be to translate the value to the boolean string whenever you want to print it, and keep the number otherwise, with sub to_bool_str { \$_[0] ? "true" : "false" }; print "1 is ", to_bool_str (1);

Re: Evaluate arbitrary boolean expressions
by tybalt89 (Priest) on Mar 13, 2018 at 15:23 UTC

Is this the kind of thing you are looking for?

```#!/usr/bin/perl

# http://perlmonks.org/?node_id=1210791

use strict;
use warnings;

sub error { die s/\G/ *** Expected @_ -->/r, "\n" }
sub want { /\G\s+/gc; /\G\Q\$_[1]\E/gc ? shift : error "'\$_[1]'" }

sub expr
{
my \$p = shift;
/\G\s+/gc;
my \$value =
/\G(T|F)/gc ? \$1 :
/\G\(/gc    ? want expr(0), ')' :
error "Operand";
\$value =
/\G\s+/gc             ? \$value :
\$p <= 1 && /\G\&\&/gc ? \$value eq 'T' ? expr(2) : (expr(2), 'F') :
\$p <= 0 && /\G\|\|/gc ? \$value eq 'T' ? (expr(1), 'T') : expr(1) :
return \$value while 1;
}

while(<DATA>)
{
my \$answer = expr(0);
/\G\s*\z/ or error "Complete Parse";
print tr/\n//dr, " = \$answer\n";
}

__DATA__
(T && F) || (F && F)
(T && T) || (F && F)
(T && F) || T

Outputs:

```(T && F) || (F && F) = F
(T && T) || (F && F) = T
(T && F) || T = T
Re: Evaluate arbitrary boolean expressions
by choroba (Bishop) on Mar 13, 2018 at 17:44 UTC
If you don't want to use eval for security purposes, write a parser. Marpa::R2 is a module that can help you with that:
```#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };

use Marpa::R2;

my \$dsl = << '__DSL__';

:default ::= action => ::first
lexeme default = latm => 1

Exp         ::= Term
| Exp (disj) Term     action => disj
Term        ::= Factor
| Term (conj) Factor  action => conj
Factor      ::= Atom
| Negation
| Bracketed
Bracketed   ::= (lbra) Exp (rbra)
Negation    ::= (excl) Factor       action => neg
Atom        ::= true                action => true
| false               action => false

true  ~ 'T'
false ~ 'F'
excl  ~ '!'
conj  ~ '&&'
disj  ~ '||'
lbra  ~ '('
rbra  ~ ')'

ws    ~ [\s]+

__DSL__

sub true   { 1 }
sub false  { 0 }
sub neg    { ! \$_[1] }
sub conj   { \$_[1] && \$_[2] }
sub disj   { \$_[1] || \$_[2] }

my \$grammar = 'Marpa::R2::Scanless::G'->new({source => \\$dsl});

my \$input = '((T) || (!(T))) && !(F && F && F && F && ! (T))';

my \$value = \${ \$grammar->parse(\\$input, 'main') };

say \$value ? 'TRUE' : 'FALSE';

```(\$q=q:Sq=~/;[c](.)(.)/;chr(-||-|5+lengthSq)`"S|oS2"`map{chr |+ord
}map{substrSq`S_+|`|}3E|-|`7**2-3:)=~y+S|`+\$1,++print+eval\$q,q,a,
Re: Evaluate arbitrary boolean expressions
by Marshall (Abbot) on Mar 13, 2018 at 16:30 UTC
It's been maybe 25 years since I wrote a prefix(algebraic) to postfix (RPN) routine to parse an algebraic expression. I would have to work on this for awhile to get it working.

Example using stack:  (2+3)*5 results in: push 2, push 3, add, push 5, multiply This requires an op precedence table.

I think you are better off with some form of Perl eval if the actual equation is unknown until runtime.

As another technique, for 8 variables, you can make an array of say 256 entries, use one bit for each variable, precalculate the results for the 8 variables and use a simple lookup table for the result.

This is also possible with a Perl hash table. Just calculate values where the 8 or whatever variables describe a "true" result.

Re: Evaluate arbitrary boolean expressions
by Anonymous Monk on Mar 13, 2018 at 12:42 UTC
If you need to evaluate an arbitrary and unforeseen expression, eval an assignment-statement. (And, arrange to catch any runtime errors that may result.)

Create A New User
Node Status?
node history
Node Type: perlquestion [id://1210791]
Front-paged by Corion
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (11)
As of 2018-06-25 20:07 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Should cpanminus be part of the standard Perl release?

Results (128 votes). Check out past polls.

Notices?