How to evaluate a string as a simple logical expression

Question

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];
    }
}

Answer 1

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

<?php

class Evaluator {
    private array $_token_fns;

    private static function filter($var){
        return $var !== null;
    }

    private static array $_find = ['/(\()/', '/^/', '/(\))/', '/$/', '/(&&)/', '/(\|\|)/'];
    private static array $_repl = ['$1 ( (', '( ( ', ') ) $1', ' ) )', ') $1 (', ') ) $1 ( (' ];

    public function __construct() {
        $value_fns = [
            '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');
            },
        ];

        $this->_token_fns = [
            'boolean' => $value_fns,
            'NULL' => $value_fns,
            'object' => [ // PHP says callables/callback functions are objects
                '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]; },
            ],
        ];
    }

    private function reducer($carry, $item) {
        return $this->_token_fns[(gettype($carry[0]))][$item]($carry);
    }

    public function strictEval($expression) {
        $fixed_expr = preg_replace(static::$_find, static::$_repl, trim($expression));
        $expr_array = preg_split('/\s+/', $fixed_expr, -1, PREG_SPLIT_NO_EMPTY);
        return array_reduce($expr_array, [$this, 'reducer'], [null])[0];
    }
}

function tester ($expression) {
    $eval = New Evaluator();
    return $eval->strictEval($expression) === eval("return {$expression};");
}

var_dump(tester('TRUE && ! TRUE || FALSE && TRUE'));

var_dump(tester('( TRUE && ! ( FALSE || ! TRUE ) )'));

var_dump(tester('( TRUE && ! TRUE ) || ( ( ( FALSE || TRUE ) || ( TRUE && FALSE ) ) || FALSE ) || FALSE && TRUE'));

var_dump(tester('TRUE && ! FALSE || TRUE || TRUE && FALSE'));