I need to evaluate string logical expressions that may contain any valid combinations of the tokens: TRUE, FALSE, !, &&, ||, ( and ). These tokens are always separated by whitespace. When fed into PHP's eval function (eval("return {$expression};")
), they return the expected Boolean result. Since this is occurring in a loop, I want to avoid the memory leak caused by using the eval function. My current implementation lacks support for parenthesis and ignores the correct order of operations for evaluating such an expression; it strictly works from left to right. It should evaluate in the order of parenthesis, !, &&, then ||.
<?php
class Evaluator {
public function __construct() {
$this->_token_fns = [
'TRUE' => function ($carry) {
return is_callable($carry) ? $carry(true) : true;
},
'FALSE' => function ($carry) {
return is_callable($carry) ? $carry(false) : false;
},
'&&' => function ($carry) {
return function ($next_carry) use ($carry) {
return $carry && $next_carry;
};
},
'||' => function ($carry) {
return function ($next_carry) use ($carry) {
return $carry || $next_carry;
};
},
'!' => function ($carry) {
return function ($next_carry) use ($carry) {
return is_callable($carry) ? $carry(!$next_carry) : !$next_carry;
};
},
'(' => function ($carry) {},
')' => function ($carry) {},
];
}
private function reducer($carry, $item) {
return $this->_token_fns[$item]($carry);
}
public function strictEval($expression) {
$expr_array = preg_split('/\s+/', $expression, -1, PREG_SPLIT_NO_EMPTY);
return array_reduce($expr_array, [$this, 'reducer'], []);
}
}
$moo = New Evaluator();
var_dump($moo->strictEval('TRUE && ! FALSE || ( TRUE || FALSE ) || TRUE && FALSE'));
UPDATE
I think I figured out how to implement parentheses.
<?php
class Evaluator {
private array $_token_fns;
public function __construct() {
$this->_token_fns = [
'callable' => [
'TRUE' => function ($carry) {
$actor = array_shift($carry);
return [$actor(true), ...$carry];
},
'FALSE' => function ($carry) {
$actor = array_shift($carry);
return [$actor(false), ...$carry];
},
'!' => function ($carry) {
$actor = array_shift($carry);
return [function ($next_carry) use ($actor) { return $actor(!$next_carry); }, ...$carry];
},
'(' => function ($carry) { return [null, ...$carry]; },
],
'value' => [
'TRUE' => function($carry) {
array_shift($carry);
return [true, ...$carry];
},
'FALSE' => function($carry) {
array_shift($carry);
return [false, ...$carry];
},
'&&' => function ($carry) {
$actor = array_shift($carry);
return [function ($next_carry) use ($actor) {
return $actor && $next_carry;
}, ...$carry];
},
'||' => function ($carry) {
$actor = array_shift($carry);
return [function ($next_carry) use ($actor) {
return $actor || $next_carry;
}, ...$carry];
},
'!' => function ($carry) {
array_shift($carry);
return [function ($next_carry) { return !$next_carry; }, ...$carry];
},
'(' => function ($carry) { return [null, $carry]; },
')' => function ($carry) {
$value = array_shift($carry);
$prev_carry = array_shift($carry);
return is_callable($prev_carry) ?
[$prev_carry($value), ...$carry] :
array_filter([$value] + $prev_carry + $carry, 'Evaluator::filter');
},
],
];
}
private static function filter($var){
return $var !== null;
}
private function reducer($carry, $item) {
return $this->_token_fns[(is_callable($carry[0]) ? 'callable' : 'value')][$item]($carry);
}
public function strictEval($expression) {
$expr_array = preg_split('/\s+/', trim($expression), -1, PREG_SPLIT_NO_EMPTY);
return array_reduce($expr_array, [$this, 'reducer'], [null])[0];
}
}
The simple solution for enforcing order of operations was to do what Fortran does and "fully parenthesize" the expression before evaluating. https://en.wikipedia.org/wiki/Operator-precedence_parser#Alternative_methods