javascript - 树结构的转换

Question

我正在处理我的 QueryBuilder JavaScript 库 ( https://github.com/mistic100/jQuery-QueryBuilder/issues/59 ) 的问题。

目标是通过 SQL 语句填充构建器。为此，我使用 https://github.com/forward/sql-parser将 WHERE 子句转换为 AST。

现在我的问题是我需要将这个 AST(一种二叉树)转换为 QueryBuilder 的内部格式(我不知道技术名称)。但我很笨，找不到可行的算法。

所以我来这里是为了找到擅长这个的人!我只需要转换数据结构的主要算法，转换值和运算符格式不会有问题。

注意事项:

• 深度不限
• 组条件(当然)只是 AND 和 OR
• 虽然规则的顺序并不重要，但应该保留

输入的SQL是(测试用例):

name LIKE "Mistic%" 
AND price BETWEEN 100 AND 200 
AND (
  category IN(1,2)
  OR parent <= 0
) 
AND id is not null

这是 SQL 解析器的输出:

{
  left: {
    left: {
      left: {
        left: {
          value: 'name'
        },
        operation: 'LIKE',
        right: {
          value: 'Mistic%'
        },
      },
      operation: 'AND',
      right: {
        left: {
          value: 'price'
        },
        operation: 'BETWEEN',
        right: {
          value: [
            {
              value: 100
            },
            {
              value: 200
            }
          ]
        }
      }
    },
    operation: 'AND',
    right: {
      left: {
        left: {
          value: 'category'
        },
        operation: 'IN',
        right: {
          value: [
            {
              value: 1
            },
            {
              value: 2
            }
          ]
        }
      },
      operation: 'OR',
      right: {
        left: {
          value: 'parent'
        },
        operation: '<=',
        right: {
          value: 0
        }
      }
    }
  },
  operation: 'AND',
  right: {
    left: {
      value: 'id'
    },
    operation: 'is not',
    right: {
      value: null
    }
  }
}

这是我需要的数据结构:

{
  condition: 'AND',
  rules: [
    {
      id: 'name',
      operator: 'like',
      value: 'Mistic%'
    },
    {
      id: 'price',
      operator: 'between',
      value: [100, 200]
    },
    {
      condition: 'OR',
      rules: [
        {
          id: 'category',
          operator: 'in',
          value: [1, 2]
        },
        {
          id: 'parent',
          operator: 'less_or_equal',
          value: 0
        }
      ]
    },
    {
      id: 'id',
      operator: 'not_null',
      value: null
    }
  ]
}

Answer 1

我想我可以正常工作了，这是伪代码:

var out = {
  condition: null
  rules: []
}
var curr = out

function flatten(node, level)
  if node.operation = 'AND' or node.operation = 'OR' then
    if level > 0 and curr.condition != node.operation then
      curr.rules.push({
        condition: null
        rules: []
      })
      curr = curr.rules.end()
    end if

    curr.condition = node.operation

    level++;

    var next = curr
    flatten(node.right, level)

    curr = next
    flatten(node.left, level)
  else
    curr.rules.push({
      id: node.left.value
      operator: node.operation
      value: node.right.value
    })
  end if
end function

flatten(parsed, 0)

这是一个自调用递归函数，当运算符在 AND 和 OR 之间变化时创建子组，并且在展平左右部分时在右子组中工作有点小技巧。