javascript - 遍历 json 抽象语法树构建布尔表达式

Question

在对谷歌和堆栈溢出进行了数小时的研究之后，我得出结论，以下 JSON 结构正确地描述了布尔表达式。我不是非常热衷于算法，但是在英语（和/或 javascript）中，您将如何递归遍历树来重建表达式，因此，在此示例中，表达式将显示为：

13 或 14 或（18 和 20 和 19）

var booleanExpression = {
    op   : 'or',
    left : {
        op  : 'or',
        left: {
            op   : 'or',
            left : {
                op   : 'literal',
                value: '14'
            },
            right: {
                op   : 'and',
                left : {
                    op   : 'and',
                    left : {
                        op   : 'literal',
                        value: '20'
                    },
                    right: {
                        op   : 'literal',
                        value: '19'
                    }
                },
                right: {
                    op   : 'literal',
                    value: '18'
                }
            }
        }
    },
    right: {
        op   : 'literal',
        value: '13'
    }
};

Answer 1

递归是评估表达式树的朋友。您需要做的就是处理各个操作类型并推迟对其子项的递归评估。通常，解析/评估事物的困难部分是将其变成基于树的结构。之后，递归地遍历树就很容易了：

function eval_expr(expr) {
  if( !expr ) { return false; }
  var op = expr.op;
  if( op == 'literal' ) {
    return expr.value;
  } else if( op == 'or' ) {
    return "(" + eval_expr(expr.left) + ") or (" + eval_expr(expr.right) + ")";
  } else if( op == 'and' ) {
    return "(" + eval_expr(expr.left) + ") and (" + eval_expr(expr.right) + ")";
  }
  console.error("Unhandled op:" + expr.op);
}


> eval_expr(booleanExpression);
"(((14) or (((20) and (19)) and (18))) or (false)) or (13)"

请注意，此函数将非零“文字”类型值视为真，零值视为假。