CODEWITHSUNDEEP
phpboolean-logic
EOB
EOB

Reputation: 3085

Evaluate logic expression given as a string in PHP

I have an object which has a state property, for example state = 'state4' or state = 'state2'.

Now I also have an array of all available states that the state property can get, state1 to state8 (note: the states are not named stateN. They have eight different names, like payment or canceled. I just put stateN to describe the problem).

In addition to that, I have a logical expression like $expression = !state1||state4&&(!state2||state5) for example. This is the code for the above description:

$state = 'state4';
$expression = '!state1||state4&&(!state2||state5)';

Now I want to check if the logical expression is true or false. In the above case, it's true. In the following case it would be false:

$state = 'state1';
$expression = state4&&!state2||(!state1||state7);

How could this be solved in an elegant way?

Upvotes: 6

Views: 4406

Answers (3)

Ersin
Ersin

Reputation: 124

I think you have a case which can be solved if you model each of your expressions as a rooted directed acyclic graph (DAG).

I assumed acyclic since your ultimate aim is to find the result of boolean algebra operations (if cycling occur in any of graph, then it'd be nonsense I think).

However, even if your graph structure—meaningfully—can be cyclic then your target search term will be cyclic graph, and it should still have a solution.

$expression = '!state1||state4&&(!state2||state5)';

And you have one root with two sub_DAGs in your example.

EXPRESSION as a Rooted DAG:

          EXPRESSION
              |
             AND
        ___/     \___
      OR             OR
     /  \           /  \
! S_1    S_4     ! S_2  S5

Your adjacency list is:

expression_adj_list = [
    expression => [ subExp_1, subExp_2 ] ,
    subExp_1 => [ ! S_1, S_4 ],
    subExp_2 => [ ! S_2, S5 ]
]

Now you can walk through this graph by BFS (breadth-first search algorithm) or DFS (depth-first search algorithm) or your custom, adjusted algorithm.

Of course you can just visit the adjacency list with keys and values as many times as you need if this suits and is easier for you.

You'll need a lookup table to teach your algorithm that. For example,

  • S2 && S5 = 1,
  • S1 or S4 = 0,
  • S3 && S7 = -1 (to throw an exception maybe)

After all, the algorithm below can solve your expression's result.

$adj_list = convert_expression_to_adj_list();
// can also be assigned by a function.
// root is the only node which has no incoming-edge in $adj_list.
$root = 'EXPRESSION';
q[] = $root; //queue to have expression & subexpressions
$results = [];
while ( ! empty(q)) {
    $current = array_shift($q);
    if ( ! in_array($current, $results)) {
        if (isset($adj_list[$current])) { // if has children (sub/expression)
            $children = $adj_list[$current];
            // true if all children are states. false if any child is subexpression.
            $bool = is_calculateable($children);
            if ($bool) {
                $results[$current] = calc($children);
            }
            else {
                array_unshift($q, $current);
            }
            foreach ($children as $child) {
                if (is_subexpresssion($child) && ! in_array($child, $results)) {
                    array_unshift($q, $child);
                }
            }
        }
    }
}
return $results[$root];

This approach has a great advantage also: if you save the results of the expressions in your database, if an expression is a child of the root expression then you won't need to recalculate it, just use the result from the database for the child subexpressions. In this way, you always have a two-level depth DAG (root and its children).

Upvotes: 1

Andrew Zhilin
Andrew Zhilin

Reputation: 1708

I am using ExpressionLanguage, but there are few different solutions

  1. ExpressionLanguage Symfony Component - https://symfony.com/doc/current/components/expression_language.html

    • cons - weird array syntax - array['key']. array.key works only for objects
    • cons - generate notice for array['key'] when key is not defined
    • pros - stable and well maintainer

  2. https://github.com/mossadal/math-parser

  3. https://github.com/optimistex/math-expression

Please remember that eval is NOT an option, under NO circumstances. We don't live an a static world. Any software always grows and evolves. What was once considered a safe input an one point may turn completely unsafe and uncontrolled.

Upvotes: 1

Eugen Rieck
Eugen Rieck

Reputation: 65274

//Initialize
$state = 'state4';
$expression = '!state1||state4&&(!state2||state5)';

//Adapt to your needs
$pattern='/state\d/';

//Replace
$e=str_replace($state,'true',$expression);
while (preg_match_all($pattern,$e,$matches)
   $e=str_replace($matches[0],'false',$e);

//Eval
eval("\$result=$e;");
echo $result;

Edit:

Your update to the OQ necessitates some minor work:

//Initialize
$state = 'payed';
$expression = '!payed||cancelled&&(!whatever||shipped)';

//Adapt to your needs
$possiblestates=array(
   'payed',
   'cancelled',
   'shipped',
   'whatever'
);

//Replace
$e=str_replace($state,'true',$expression);
$e=str_replace($possiblestates,'false',$e);

//Eval
eval("\$result=$e;");
echo $result;

Edit 2

There has been concern about eval and PHP injection in the comments: The expression and the replacements are completly controlled by the application, no user input involved. As long as this holds, eval is safe.

Upvotes: 2

Related Questions