Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Evaluate expression tree in Javascript

I have input consisting of nested logical expression objects

Ex:

var obj = {
  'OR': [
      {
        'AND': [
            false, true, true
        ]
      },
      {
        'OR': [
            true, false, false, {
                'AND': [true, true]
            }
        ]
      },
      true
  ]
};

Which is equivalent to ((false && true && true) || (true || false || false || (true && true)) || true)

We need to write a function that calculates this

Approach:

Go to the innermost level and evaluate it first, moving to the top

var expressionEvaluator = function(opArr){
            var hasChildObjects = function(arr){
                if(Array.isArray(arr)){
                    return arr.some(function(obj){
                        return typeof(obj) === 'object';
                    });
                }
                else if(typeof(arr) === 'object'){
                    return true;
                }
            };
            var evaluateArr = function(list, operator){
                var result;
                if(operator === 'AND'){
                    result = true;
                    for(var i = 0; i<list.length; i++){
                        if(!list[i]){
                            result = false;
                        }
                    }
                }
                else if(operator === 'OR'){
                    result = false;
                    for(var i = 0; i<list.length; i++){
                        if(list[i]){
                            result = true;
                        }
                    }
                }
                return result;
            };
            var iterate = function(opArr){
                Object.keys(opArr).forEach(function(k){
                    if(hasChildObjects(opArr[k])){
                        iterate(opArr[k]);
                    }
                    else{
                        opArr = evaluateArr(opArr[k], k);
                    }
                });
            };
            iterate(opArr);
            return result;
        }

I am able to reach the innermost object and evaluate it but not reach back to the topmost level and evaluate the entire expression object.

like image 835
user544079 Avatar asked Dec 09 '20 06:12

user544079


People also ask

How do you evaluate a tree expression?

We can evaluate an expression tree by applying the operator at the root to values obtained by recursively evaluating left and right subtrees. This can be easily done by traversing the expression tree using postorder traversal.

What is expression tree give example?

Each node in an expression tree is an expression. For example, an expression tree can be used to represent mathematical formula x < y where x, < and y will be represented as an expression and arranged in the tree like structure. Expression tree is an in-memory representation of a lambda expression.

What is an expression tree in data structure?

An expression tree is a representation of expressions arranged in a tree-like data structure. In other words, it is a tree with leaves as operands of the expression and nodes contain the operators. Similar to other data structures, data interaction is also possible in an expression tree.


Video Answer


5 Answers

You could use a simple recursive function.

  • If the current object has OR key, then check if some of the items in the array are truthy.
  • If AND, check if every item is truthy.
  • If one of the item in the array is an object, recursively call the function on the object to get its value

const input={OR:[{AND:[false,true,true]},{OR:[true,false,false,{AND:[true,true]}]},true]};

function evaluate({ OR, AND }) {
  if (OR)
    return OR.some(c => typeof c === 'object' ? evaluate(c) : c)
  if (AND)
    return AND.every(c => typeof c === 'object' ? evaluate(c) : c)
}

console.log(evaluate(input))

Since the callback functions are same, you could also get the operation to a variable and call it dynamically:

function evaluate({ OR, AND }) {
  const array = OR ?? AND,
        operation = OR ? 'some' : 'every';
  
  return array[operation](c => typeof c === 'object' ? evaluate(c) : c)
}

OR

const evaluate = ({ OR, AND }) => OR ? OR.some(callback) : AND.every(callback),
      callback = c => typeof c === 'object' ? evaluate(c) : c
like image 196
adiga Avatar answered Oct 22 '22 12:10

adiga


Another variant on the theme here:

const evaluate = (tree) =>
  typeof tree === 'boolean'
    ? tree
  : 'OR' in tree
    ? tree .OR .some (evaluate)
  : 'AND' in tree
    ? tree .AND .every (evaluate)
  : false // or throw an error?

const tree = {OR: [{AND: [false, true, true]}, {OR: [true, false, false, {AND: [true, true]}]}, true]}

console .log (evaluate (tree))

evaluate returns the value supplied if it's a boolean. Otherwise it checks for 'OR' or 'AND' nodes, and handles them appropriately. There is a catch-all at the end for non-well-formed trees. Here I return false, but you might throw an error, return null, or something else.

If you don't need that catch-all, this can be simplified to a one-liner:

const evaluate = (tree) =>
  typeof tree == 'boolean' ? tree: tree.OR ? tree.OR .some (evaluate) : tree.AND .every (evaluate)

But I'm concerned by the tree structure. I always worry when there are objects that can only have one property. It feels like an array is then a better design.

This alternative feels cleaner:

const tree = [
  'OR', 
  [
    ['AND', [false, true, true]], 
    ['OR', [true, false, false, ['AND', [true, true]]]], 
    true
  ]
]

And that could be evaluated with similar code:

const evaluate = (tree) =>
  typeof tree == 'boolean' ? tree : tree [1] [tree [0] === 'OR' ? 'some' : 'every'] (evaluate)

Update: A comment from customcommander pointed out that even this array format is overcomplicated.

If instead, we were dealing with something like this:

const tree = [
  'OR', 
  ['AND', false, true, true], 
  ['OR', true, false, false, ['AND', true, true]], 
  true
]

then we could use a version like this:

const evaluate = (tree) =>
  typeof tree === 'boolean' 
    ? tree 
    : tree .slice (1) [tree [0] === 'OR' ? 'some' : 'every'] (evaluate)
like image 41
Scott Sauyet Avatar answered Oct 22 '22 11:10

Scott Sauyet


Not sure if this is a good solution but I thought we could be a bit "lazy" and avoid unnecessary recursion which may or may not help depending on the size of your expression tree.

In the following expression there is no need to evaluate both A & B since C is already true:

{OR: [{/* ... */}, {/* ... */}, true]}
//    ^            ^            ^
//    A            B            C

Similarly there is no need to evaluate both A & B since C is already false:

{AND: [{/* ... */}, {/* ... */}, false]}
//     ^            ^            ^
//     A            B            C

With that in mind I came up with the following code:

const lazy_or = exp => exp.find(e => e === true);
const lazy_and = exp => exp.find(e => e === false);

const evaluate =
  exp =>
      typeof exp === "boolean"                ? exp
    : exp.OR && lazy_or(exp.OR)               ? true
    : exp.OR                                  ? exp.OR.some(evaluate)
    : exp.AND && lazy_and(exp.AND) === false  ? false
                                              : exp.AND.every(evaluate);
like image 2
customcommander Avatar answered Oct 22 '22 11:10

customcommander


function evalOBJ(obj) {
    let result = true;
    if (obj.OR) {
        result = false;
        for (const v of obj.OR) {
            if (typeof v === 'object') {
                result = result || evalOBJ(v);
            } else {
                result = result || v;
            }
        }
    } else if (obj.AND) {
        for (const v of obj.AND) {
            if (typeof v === 'object') {
                result = result && evalOBJ(v);
            } else {
                result = result && v;
            }
        }
    }
    return result;
}
like image 1
t348575 Avatar answered Oct 22 '22 11:10

t348575


This is fundamentally the same operation as adiga's answer but variation uses mutual recursion between evaluate and the operator functions. The main benefit is separation between the algorithm traversing the tree evaluate and the actual operators used. It's easier to refactor to handle other operations if needed, by just adding them to operators.

const operators = {
  "OR" : arr => arr.some(evaluate),
  "AND": arr => arr.every(evaluate),
}

function evaluate(input) {
  if (typeof input !== "object") 
    return input;
  
  const [op, value] = Object.entries(input)[0];
  return operators[op](value);
}

test(true);
test(false);
test({"OR": [false, true]});
test({"OR": [false, false]});

test({"AND": [true, true]});
test({"AND": [false, true]});

test({
  'OR': [
      {
        'AND': [
            false, true, true
        ]
      },
      {
        'OR': [
            true, false, false, {
                'AND': [true, true]
            }
        ]
      },
      true
  ]
})

function test(input) {
  console.log(`evaluating: ${JSON.stringify(input, undefined, 2)}
  result: ${evaluate(input)}`)
}

To showcase the ease of extension, we can convert this to also handle mathematical operations by just adding operators that handle addition and multiplication:

const operators = {
  "OR" : arr => arr.some(evaluate),
  "AND": arr => arr.every(evaluate),
  "+": arr => arr.reduce((a, b) => a + evaluate(b), 0),
  "*": arr => arr.reduce((a, b) => a * evaluate(b), 1),
}

function evaluate(input) {
  if (typeof input !== "object") 
    return input;
  
  const [op, value] = Object.entries(input)[0];
  return operators[op](value);
}

test({"+": [2, 3]});
test({"*": [2, 3]});
test({
  '+': [
      {
        '*': [
            2, 2, 5
        ]
      },
      {
        '+': [
            6, 4, 3, {
                '*': [1, 7]
            }
        ]
      },
      2
  ]
})

function test(input) {
  console.log(`evaluating: ${JSON.stringify(input, undefined, 2)}
  result: ${evaluate(input)}`)
}
like image 1
VLAZ Avatar answered Oct 22 '22 12:10

VLAZ