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

Traversing a json abstract syntax tree to build boolean expression

本文关键字：构建 布尔表达式 语法树 json 抽象 遍历      更新时间：2023-09-26

在对google和堆栈溢出做了几个小时的研究之后，我得出结论，下面的JSON结构正确地描述了一个布尔表达式。我不是很热衷于算法，但在英语(和/或javascript)中，如何递归遍历树来重建表达式，因此，在本例中，表达式将为:

13 or 14 or (18 and 20 and 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'
    }
};

递归是求表达式树的好朋友。您所需要做的就是处理单个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)"

注意，该函数将非零的'literal'类型值视为真值，将零值视为假值。

相关文章：