Алгоритм решения булевых переменных в переполнении стека

Question

Алгоритм решения булевых переменных в переполнении стека

Приведенный ниже ассоциативный массив представляет различные переменные (определяемые значениями ключей) и их соответствующие логические операторы для сравнения со своими соседями — их соседями являются переменные под ними.

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;

Я просто хотел еще раз взглянуть на это, чтобы убедиться, что вышеприведенное имеет смысл — я запускал этот алгоритм несколько раз, и казалось, что было несколько раз, когда он не возвращал правильное логическое значение.

1

algorithm boolean-expression boolean-logic php

Решение

Другие решения

То, что вы пытаетесь реализовать, называется Абстрактное синтаксическое дерево. Это используется, в частности, для создания компиляторов и интерпретаторов. Это практическое представление для вашего типа проблемы, потому что оно может обрабатывать приоритет оператора, что затрудняется вашим плоским представлением.

В вашем случае, читая ваш код, мы видим, что все операторы имеют одинаковый приоритет слева, а ваш массив анализируется слева направо, поэтому

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

1

Источник

Accepted Answer

Это почти страшно сказать вслух, но вы нашли один из тех редких случаев, когда eval на самом деле является действительным решением, а не проблема сама по себе. Просто «компилирование» вашего ввода в 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 на $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);

Что совершенно безопасно и короче всего, что вы могли бы придумать.

2