在 Javascript 中评估表达式树

Question

我的输入由嵌套的逻辑表达式对象组成

例如：

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

相当于((false && true && true) || (true || false || false || (true && true)) || true)

我们需要编写一个函数来计算这个

方法：

先到最里面评价，移到最上面

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

我能够到达最里面的对象并对其求值，但无法回到最顶层并求值整个表达式对象。

Answer 1

您可以使用简单的递归函数。

如果当前对象有OR键，则检查数组中的some项是否为truthy.
如果 AND，检查 every 项是否为 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))

由于回调函数是一样的，你也可以把操作拿到一个变量上动态调用：

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

或

const evaluate = ({ OR, AND }) => OR ? OR.some(callback) : AND.every(callback),
      callback = c => typeof c === 'object' ? evaluate(c) : c

Answer 2

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

Answer 3

这基本上与相同的操作，但变化使用 evaluate 和运算符函数之间的相互递归。主要好处是遍历树 evaluate 的算法与实际使用的运算符之间的分离。如果需要，通过将它们添加到 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)}`)
}

为了展示扩展的便利性，我们可以将其转换为也可以处理数学运算，只需添加处理加法和乘法的运算符即可：

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)}`)
}

Answer 4

不确定这是否是一个好的解决方案，但我认为我们可以有点“懒惰”并避免不必要的递归，这可能有帮助也可能没有帮助，具体取决于表达式树的大小。

在下面的表达式中，不需要计算 A 和 B，因为 C 已经为真：

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

同样，没有必要同时评估 A 和 B，因为 C 已经错误：

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

考虑到这一点，我想出了以下代码：

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

Answer 5

此处主题的另一个变体：

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 提供的值（如果它是布尔值）。否则它会检查 'OR' 或 'AND' 节点，并适当地处理它们。对于格式不正确的树，最后有一个包罗万象的东西。我在这里 return false，但你可能会抛出一个错误，return null，或者别的什么。

如果你不需要那个包罗万象的东西，这可以简化为一行：

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

但我担心树结构。我总是担心有些对象只能有一个属性。感觉数组才是更好的设计

这个替代方案感觉更干净：

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

这可以用类似的代码进行评估：

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

更新：来自customcommander的指出即使这种数组格式也过于复杂。

如果相反，我们正在处理这样的事情：

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

那么我们可以使用这样的版本：

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

在 Javascript 中评估表达式树

Evaluate expression tree in Javascript

javascript

recursion

expression-trees