current community

your communities

more stack exchange communities

Stack Exchange
tour help
stack overflow careers
Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 1 down vote favorite

The associative array below represents different variables (identified by the key values) and their respective logical operators to compare with their neighbors - their neighbors being the variables below them.

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

I'm trying to figure out an algorithm that would take the data structure above and translate it to the following expression:

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

Where lookup( $id ) is a function that looks up the boolean value of the given string $id and returns it. So if x = true, y = true, z = false, and v = false, then the above would evaluate to:

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

This is what I have thus far:

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

Just wanted another set of eyes on this to make sure the above makes sense - I've run this algorithm a number of times and it seemed like there were a few times where it didn't return the proper boolean value.

share|improve this question
    
In which language does v come afer z ? –  Cups Dec 7 '14 at 0:58

2 Answers 2

up vote 2 down vote accepted

It's almost scary to say out loud, but you found one of those rare cases where eval is actually a valid solution instead of a problem on its own. Just 'compiling' your input to PHP will make your life a thousand times easier.

For example:

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

I am of course assuming here the input is trusted, otherwise you'll need some proper validation to prevent arbitrary code injection. A simple ctype_alpha on $value would probably suffice though.

Actually with your lookup function it becomes even easier:

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

Which is completely safe, and shorter than anything else you could come up with.

share|improve this answer
up vote 1 down vote

What you are trying to implement is called an Abstract Syntax Tree. This is used in particular to make compilers and interpreters. It is a practical representation for your type of problem, because it can handle operator precedence, which is made hard by your flat representation.

In your case, by reading your code, we can see that all operators have the same left precedence and your array is parsed from left to right, so

true || true && false || false

is evaluated by your algorithm as:

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

which evaluates as false.

I highly suggest you to not use a flat syntax to represent operands and operators, but a tree-based structure so you can handle priority and grouping parentheses, such as:

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

which would represent:

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

This recursive code could evaluate it:

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);
share|improve this answer
1  
In PHP, && has higher precedence than ||, so the example I gave would evaluate to true. Point taken as far as the AST though. For my particular application, I'm not interested in grouping or priority, just to get the overall result of the boolean expression. –  rafiki_rafi Dec 7 '14 at 4:23
    
I know about the precedence of those operators, I just made up examples without being 100% accurate with your question :) –  SirDarius Dec 7 '14 at 9:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.