Преобразование древовидных структур

Question

Я работаю над проблемой для моей JavaScript-библиотеки QueryBuilder (https://github.com/mistic100/jQuery-QueryBuilder/issues/59).

Целью является заполнить построитель из инструкции SQL. Для этого я использую https://github.com/forward/sql-parser для преобразования предложения WHERE в AST.

Теперь моя проблема в том, что мне нужно преобразовать этот AST (который является своего рода двоичным деревом) во внутренний формат QueryBuilder (я не знаю технического названия). Но я тупой, и я не могу найти рабочий алгоритм.

Итак, я здесь, чтобы найти человека, который хорош в этом! Мне просто нужен основной алгоритм для преобразования структуры данных, преобразование значений и формат операторов не будет проблемой.

Примечания:

• Глубина не ограничивается
• условия группы являются (конечно) только И и ИЛИ
• Хотя порядок правил не важно, она должна быть сохранена

вход SQL является (тест):

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

Это выход SQL Parser:

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

Это рекурсивная функция самосогласования, создающая подгруппы, когда оператор меняется между И и OR, и небольшая битка для работы в правой подгруппе при выравнивании левой и правые части.