首页 文章

在PHP中求解布尔变量的算法

提问于
浏览 次
1

下面的关联数组表示不同的变量（由键值标识）和它们各自的逻辑运算符以与它们的邻居进行比较 - 它们的邻居是它们下面的变量 .

Array(
      [x] => or
      [y] => and
      [z] => or
      [v] => null
     )

我正在试图找出一种算法，它将采用上面的数据结构并将其转换为以下表达式：

$result = lookup('x') || lookup('y') && lookup('z') || lookup('v');

其中 lookup( $id ) 是一个查找给定字符串 $id 的布尔值并返回它的函数 . 因此，如果x = true，y = true，z = false，并且v = false，那么上面将评估为：

$results = true || true && false || false; // should evaluate to true

这是我到目前为止：

$bool_vars = array( 'x' => 'or', 'y' => 'and', 'z' => 'or', 'v' => null);

$keys = array_keys( $bool_vars ); // Grab the variable identifiers
$result = lookup( $keys[0] ); // Get the bool value of the first variable

// If there is more than one var, we need to evaluate the boolean expression
if( count($keys) > 1 ){
    foreach( $keys as $k => $key ){

        // No need to evaluate the last element since it has no neighbor
        if( $k + 1 == count( $keys ) ){ break; }

        $operator = $bool_vars[ $key ]; // Get the logical operator to use

        // Filter by operator
        switch( $operator ){
            case 'or':

                // Get the bool value of the next var
                $result = $result || isset( lookup( $keys[$k + 1] ) ); 
                break;

            case 'and':

                $result = $result && isset( $lookup( $keys[$k + 1] ) );
                break;

            default:
                continue;
        }
    }
}

return $result;

只是想要另一组眼睛，以确保上述有意义 - 我已经多次运行这个算法，似乎有几次它没有返回正确的布尔值 .

php algorithm boolean-logic boolean-expression

2 回答

  • 2

    大声说出来几乎是可怕的，但你发现其中一种罕见的情况是eval实际上是一个有效的解决方案，而不是自己的问题 . 只需'compiling'您对PHP的输入将使您的生活变得轻松一千倍 .

    例如：

    $code = 'return ';
foreach($keys as $value => $op) {
  $code .= '$'.$value;
  switch($op) {
    case 'and':  $code .= ' && '; break;
    case 'or':   $code .= ' || '; break;
  }
}
$result = eval($code);

    我当然假设输入是可信的，否则你需要一些适当的验证来防止任意代码注入 . 一个简单的 ctype_alpha on $value 可能就足够了 .

    实际上，使用 lookup 函数，它变得更加容易：

    $code = 'return ';
foreach($keys as $value => $op) {
  $code .= lookup($value) ? 'true' : 'false';
  switch($op) {
    case 'and':  $code .= ' && '; break;
    case 'or':   $code .= ' || '; break;
  }
}
$result = eval($code);

    这是完全安全的，比你想出的任何其他东西都短 .

    回复于
  • 1

    您要实现的内容称为Abstract Syntax Tree . 这尤其用于制作编译器和解释器 . 它是您的问题类型的实际表示，因为它可以处理运算符优先级，这是由您的平面表示很难实现的 .

    在您的情况下，通过阅读您的代码，我们可以看到所有运算符具有相同的左优先级，并且您的数组从左到右进行解析，因此

    true || true && false || false

    由您的算法评估为：

    ((true || true) && false) || false

    其评估结果为 false .

    我强烈建议你使用平面语法来表示操作数和运算符，但是使用基于树的结构，这样你就可以处理优先级和分组括号，例如：

    $tree = [
   'and' => [
        [ 'or' => ['x', 'y'] ],
        [ 'or' => ['z', 'v'] ]
   ]
];

    这将代表：

    (x || y) && (z || v)

    这个递归代码可以评估它：

    function evalAnd($arr) {
    return evalTree($arr[0]) && evalTree($arr[1]);
}

function evalOr($arr) {
    return evalTree($arr[0]) || evalTree($arr[1]);
}

function evalTree($tree) {
    if (is_array($tree) && array_key_exists('and', $tree)) {
        return evalAnd($tree['and']);
    }
    elseif (is_array($tree) && array_key_exists('or', $tree)) {
        return evalOr($tree['or']);
    }
    else {
        return lookup($tree);
    }
}

evalTree($tree);
    回复于

相关问题