在PHP中求解布爾變量的算法

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 =真，Z =假，和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; 

只是想另一組眼睛在這上面確定上述是有道理的 - 我已經運行了這個算法很多次，好像有幾次它沒有返回正確的布爾值。

Answer 1

大聲說出來幾乎嚇人，但是你發現了其中一種罕見的情況，其中eval實際上是一個有效的解決方案，而不是自己的問題。只需「編譯」您對PHP的輸入，就可以讓您的生活變得更容易。

例如：

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

我當然這裏假設輸入是可信的，否則你會需要一些適當的驗證，以防止任意代碼注入。 $value上的一個簡單的ctype_alpha可能就足夠了。

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

這是完全安全的，比其他任何你能想出更短。

Answer 2

你正在努力實現的是所謂的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);