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

Question

在对 google 和堆栈溢出进行了数小时的研究后，我得出以下 JSON 结构正确描述 boolean 表达式的结论。我不太热衷于算法，但在英语(和/或 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

Recursion是你评估表达式树的 friend 。您需要做的就是处理各个 op 类型并推迟对其子项的递归评估。一般来说，解析/评估事物的困难部分是将其转化为基于树的结构。之后很容易递归遍历树:

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

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