如何将字符串评估为简单的逻辑表达式

Question

我需要评估可能包含以下标记的任何有效组合的字符串逻辑表达式：TRUE、FALSE、!、&&、||、( 和 )。这些标记总是由空格分隔。当输入 PHP 的 eval 函数 (eval("return {$expression};")) 时，它们 return 预期的布尔结果。由于这是在循环中发生的，所以我想避免使用 eval 函数引起的内存泄漏。我当前的实现不支持括号，并且忽略了评估此类表达式的正确操作顺序；它严格从左到右工作。它应该按照括号、!、&&、然后是||.

的顺序求值

<?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'));

更新

我想我知道如何实现括号了。

<?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

执行操作顺序的简单解决方案是执行 Fortran 所做的事情，并在计算之前“完全括起”表达式。 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 = [' ( (', '( ( ', ') ) ', ' ) )', ')  (', ') )  ( (' ];

    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'));

如何将字符串评估为简单的逻辑表达式

How to evaluate a string as a simple logical expression

php

php-7.2