Evaluate expression tree in Javascript

Question

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.

Answer 1

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