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.
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.
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.
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.
You could use a simple recursive function.
OR
key, then check if some
of the items in the array are truthy
.AND
, check if every
item is truthy
.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
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)
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);
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;
}
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)}`)
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With