Создать вложенный json из проанализированного ввода текста

Question

Я пытаюсь создать функцию javascript для разбора текста на вложенные JSON, но я застрял в управлении этим рекурсивом.

Так что в основном преобразуйте то, что в текстовом поле:

todo list
  learn js
     hello world
shopping list
  costco
procrastination list

к этому:

[
{'val':'todo list','children':[{'val':'learn js','children':['val':'hello world']}]},
{'val':'shopping list','children':[{'val':'costco'}]},
{'val':'procrastination list'}
]

Я придумал это:

const TxtParser = txtBoxVal => {
  let txtArr = [];
  let nbrSpacesPrev = 0;
  if (txtBoxVal) {
    if (txtBoxVal.split("\n").length) {
      let lines = txtBoxVal.split("\n");
      let numNewLines = txtBoxVal.split("\n").length;
      let i;
      for (i = 0; i < numNewLines; i++) {
        if (lines[i].search(/\S/) !== -1) {
          let txtObj = {};
          txtObj["line"] = lines[i].trim();
          // check for space diff
          txtObj["nbrSpaces"] = lines[i].search(/\S/);
          txtArr.push(txtObj);
        }
      }
    }
  }
  return txtArr;
}; 

Я получаю только линейные результаты: https://codesandbox.io/s/text-to-json-parser-kuc28

Я не могу понять, как создавать вложенных детей.

Answer 1

( Редактировать : добавлена ​​строка .filter для очистки входных данных и переключен на входные данные из Thankyou, чтобы продемонстрировать это.)

---

Вот один из подходов. Мы преобразуем в промежуточный формат, который выглядит следующим образом:

[
    {indent: 0, val: "todo list"},
    {indent: 2, val: "learn js"},
    {indent: 5, val: "hello world"},
    {indent: 0, val: "shopping list"},
    {indent: 2, val: "costco"},
    {indent: 0, val: "procrastination list"}
]

, где indent s считает пробелы перед текстом в каждой строке. Затем, сохраняя стек родителей нашего последнего узла, ища первый с более низким значением отступа, чем у нашего текущего узла, и добавляя текущий узел в качестве одного из его дочерних элементов, мы складываем этот список в структуру данных, подобную этой :

{
    indent: -1,
    children: [
        {
            indent: 0,
            val: "todo list",
            children: [
                {indent: 2, val: "learn js", children: [{indent: 5, val: "hello world"}]}
            ],
        },
        {indent: 0, val: "shopping list" children: [{indent: 2, val: "costco"]},
        {indent: 0, val: "procrastination list"}
    ],
}

И, наконец, через дочерние элементы этой структуры мы удалим все вложенные indent свойства, мы получим ваш вывод.

Этот код построен на этой идее:

// Helper function
const deepMap = (fn) => ({children, ...rest}) => ({
  ... fn ({...rest}),
  ... (children ? {children: children .map (deepMap (fn))} : {})
})

// Main function
const extractTree = (text) => 
  text
    .split ('\n')
    .filter ((line) => /\S/ .test (line))
    .map (s => s .match (/^(\s*)(.*)$/) .slice (1))
    .map (([prefix, val]) => ({indent: prefix .length, val}))
    .reduce ((path, node) => {
      const {indent, val} = node
      const parentIdx = path .findIndex (node => node .indent < indent)
      const parent = path [parentIdx]
      parent .children = [... (parent .children || []), node]
      return [node, ... path .slice (parentIdx)]
    }, [{indent: -1, children: []}]) 
    .slice (-1) [0] 
    .children
    .map (deepMap (({indent, ...rest}) => ({...rest})))

// Test data
const text = `  
todo list
  learn js
    hello world
    functions
  
shopping list
  costco
  berries


  mushrooms
procrastination list
`

// Demo
console .log (
  extractTree (text)
)

.as-console-wrapper {min-height: 100% !important; top: 0}

Вызов .filter удаляет все пустые строки и те, которые содержат только пробелы. Вызов .split и два вызова .map преобразуют этот очищенный ввод в этот первый промежуточный формат. Надеюсь, они должны быть достаточно ясными. (Вы можете добавить здесь преобразование tab -> space, если это необходимо.)

Вызов .reduce является более сложным, поддерживая стек узлов-предков, начиная со значения по умолчанию с отступом -1, поэтому оно всегда будет ниже любого фактического значения, находя непосредственного родителя нашего текущего узла в стеке в качестве первого с отступом, меньшим, чем его собственный отступ, затем добавляя текущий узел в качестве дочернего элемента этого родителя и помещая его в стек.

После этого мы используем .slice (-1) [0] .children, чтобы получить дочерние элементы нижнего элемента стека, которые должны быть интересующими нас узлами.

Наконец, мы .map поверх результатов, передавая вспомогательную функцию deepMap, чтобы пройти через каждый из этих объектов и применить функцию, которую мы передаем ей, чтобы удалить ненужные indent узлы. deepMap - полезная, довольно обобщенная c функция, применяющая функцию к узлу и, рекурсивно, к каждому его дочернему элементу.

---

Это делает то, что я не часто делаю в мой код: он мутирует данные по пути. Я не придумал никакого чистого способа избежать мутации. Мы не изменяем исходные данные - мы не варвары! - но внутренние узлы видоизменяются во время вызова reduce.

Если кто-нибудь найдет чистый способ сделать это без такой мутации, я бы хотел услышать об этом!

Answer 2

IMO , самый простой подход состоит в том, чтобы просто сделать прямую for l oop, как первоначально было у ОП. Нам просто нужно использовать стек и поддерживать некоторые ссылки для достижения цели.

Плюсы: O(n) производительность и способность чтения кода.

Вот моя попытка (подробности в комментариях) :

let input = `item.1
    item.1.1
        item.1.1.1
item.2
    item.2.1
item.3
item.4
    item.4.1
        item.4.1.1
        item.4.1.2
        item.4.1.3
        
    item.4.2
        item.4.2.1
            item.4.2.1.1
                item.4.2.1.1.1

                item.4.2.1.1.2
                item.4.2.1.1.3
            item.4.2.1.2
                item.4.2.1.2.1
            item.4.2.1.3
        item.4.2.2`;

// Updated to use 2 stacks (for spaces and parent items) so that we don't include
// the spaces count in the final result.
const parseList = list => {
    const final = []; // The final result
    const parents = []; // A stack to maintain parent references.
    const spaces = []; // A stack to track parent spaces.
    let parentItem = {
        children: final // Use final reference so initial parent is a proxy to the final result
    };
    let parentSpaces = -1; // Initial space starting at -1 (which can never occur)
    let prevItem;   // The previous list item
    let prevSpaces; // The previous item's spaces

    const lines = String(list).split("\n");
    const lineCount = lines.length;

    for (let i = 0; i < lineCount; i++) {
        const line = lines[i].trim();
        const currSpaces = lines[i].search(/\S/);

        // Ignore empty lines
        if (line) {
            // Here's the magic!!
            // If the current spaces are more than the previous spaces, then this item should be a child
            // of the previous item. Also account for prevSpaces === -1 for initial iteration
            if (prevSpaces !== -1 && currSpaces > prevSpaces) {
                // Set new parent
                parents.push(parentItem);
                spaces.push(parentSpaces);
                parentItem = prevItem;
                parentSpaces = prevSpaces;
            } else {
                // If item is not a child then pop() the parents until the parent's spaces are less
                // than the current item's spaces
                while (currSpaces <= parentSpaces) {
                    parentItem = parents.pop();
                    parentSpaces = spaces.pop();
                }
            }

            // Create new list item
            const item = {
                val: line
            };

            // Add child
            parentItem.children = parentItem.children || []; // This is so the children property isn't created it no child
            parentItem.children.push(item);

            prevSpaces = currSpaces;
            prevItem = item;
        }
    }

    return final;
};

console.log(JSON.stringify(parseList(input), null, 2));

---

Ответ на @ Thankyou вызов

Давайте сравним эти 2 функции:

const max0 = (x, y, z) => x > y ? x > z ? x : z : y > z ? y : z;
// variable: 3
// mutations: 0
// variable reassignments: 0
// lines of implementation: 1

и

const max1 = (x, y, z) => {
  let max = x;
  if (y > max) max = y;
  if (z > max) max = z;
  return max;
}
// variable: 4
// mutations: 0
// variable reassignments: 2
// lines of implementation: 5

По этим показателям max0 будет считаться более простым, но будет ли это так, если вы спросите 100 случайных разработчиков? Эти метрики, хотя и объективные, не рассказывают полную историю (ie: вызовы функций, языковые особенности, зависимости и т. Д. c ...), а также не определяют субъективную концепцию человека о простоте.

Могу ли я указать некоторые вещи и использовать функции родного языка для уменьшения этих показателей c? Конечно! Но я не сделал. Я признаю, что опытные разработчики, вероятно, предпочтут ваш ответ за его элегантность, хитрость и «простоту». Но моя грубая реализация имеет другие преимущества и показывает еще один способ, которым это можно сделать при использовании элементарных конструкций. Те, кого даже такой нуб ie, как я (и, надеюсь, другие, менее старшие, чем вы), могут легко подобрать. Есть причина, по которой университеты преподают циклы for перед рекурсией. Но это только мое мнение.

Answer 3

рекурсивный подход

У вас супер веселая проблема! Я собираюсь добавить еще несколько элементов к вашему входу, чтобы мы могли видеть, что братья и сестры правильно вложены. Я также разбросал несколько пустых строк, чтобы сделать нашу программу более устойчивой -

const data = `
todo list
  learn js
    hello world
    functions

shopping list
  costco
  berries


  mushrooms
procrastination list
`

Для начала мы sanitize данных удалим все пустые строки и все начальные и конечные пробелы -

const sanitize = (str = "") =>
  str.trim().replace(/\n\s*\n/g, "\n")

console.log(sanitize(data))

todo list
  learn js
    hello world
    functions
shopping list
  costco
  berries
  mushrooms
procrastination list

Имея чистую отправную точку, мы можем начать разбирать проблему ...

---

design

Давайте подставим пробелы для • и окончания строки для ¬, чтобы мы могли видеть, что происходит. Мы начинаем с вызова makeChildren для чистой строки -

makeChildren(
  <b>todo•list¬
  ••learn•js¬
  ••••hello•world¬
  ••••functions¬
  shopping•list¬
  ••costco¬
  ••berries¬
  ••mushrooms¬
  procrastination•list</b>
)

makeChildren создает массив и вызывает make1 для каждого элемента -

[ make1(
    <b>todo•list¬
    ••learn•js¬
    ••••hello•world¬
    ••••functions¬</b>
  )
, make1(
    <b>shopping•list¬
    ••costco¬
    ••berries¬
    ••mushrooms¬</b>
  )
, make1(
    <b>procrastination•list</b>
  )
]

make1 создает узел и впоследствии вызывает makeChildren своих потомков -

[ { value: <b>todo•list</b>
  , children: makeChildren(outdent(
      <b>••learn•js¬
      ••••hello•world¬
      ••••functions¬</b>
    ))
  }
, { value: <b>shopping•list</b>
  , children: makeChildren(outdent(
      <b>••costco¬
      ••berries¬
      ••mushrooms¬</b>
    ))
  }
, { value: <b>procrastination•list</b>
  , children: makeChildren(outdent(

    ))
  }
]

И, как мы уже видели, makeChildren создает массив и вызывает make1 для каждого дочернего элемента -

[ { value: <b>todo•list</b>
  , children:
      [ make1(
          <b>learn•js¬
          ••hello•world¬
          ••functions¬</b>
        )
      ]
  }
, { value: <b>shopping•list</b>
  , children:
      [ make1(<b>costco¬</b>)
      , make1(<b>berries¬</b>)
      , make1(<b>mushrooms¬</b>)
      ]
  }
, { value: <b>procrastination•list</b>
  , children:
      []
  }
]

И время от времени взаимно рекурсивный процесс продолжается ... makeChildren вызывает make1, который вызывает makeChildren, который вызывает make1 и c, пока базовый случай не будет достигнут в каждом ответвление.

---

орудие

В соответствии с нашим проектом мы начнем с makeChildren -

const makeChildren = (str = "") =>
  str === ""
    ? []
    : str.split(/\n(?!\s)/).map(make1)

, который просит нас реализовать make1 -

const make1 = (str = "") =>
{ const [ value, children ] = cut(str, "\n")
  return { value, children: makeChildren(outdent(children)) }
}

Что требует от нас реализации cut и outdent -

• cut работает как String.prototype.split, но разбивает только str на первое вхождение char
• outdent удаляет один уровень отступа

const cut = (str = "", char = "") =>
{ const pos = str.search(char)
  return pos === -1
    ? [ str, "" ]
    : [ str.substr(0, pos), str.substr(pos + 1) ]
}

const outdent = (str = "") =>
{ const spaces = Math.max(0, str.search(/\S/))
  const re = new RegExp(`(^|\n)\\s{${spaces}}`, "g")
  return str.replace(re, "$1")
}

И это все! Окончательный result - это -

const result =
  makeChildren(sanitize(data))

console.log(result)

[ { value: "todo list"
  , children:
      [ { value: "learn js"
        , children:
            [ { value: "hello world", children: [] }
            , { value: "functions", children: [] }
            ]
        }
      ]
  }
, { value: "shopping list"
  , children:
      [ { value: "costco", children: [] }
      , { value: "berries", children: [] }
      , { value: "mushrooms", children: [] }
      ]
  }
, { value: "procrastination list", children: [] }
]

Запустите приведенный ниже фрагмент, чтобы проверить результаты в своем браузере -

const sanitize = (str = "") =>
  str.trim().replace(/\n\s*\n/g, "\n")

const cut = (str = "", char = "") =>
{ const pos = str.search(char)
  return pos === -1
    ? [ str, "" ]
    : [ str.substr(0, pos), str.substr(pos + 1) ]
}

const outdent = (str = "") =>
{ const spaces = Math.max(0, str.search(/\S/))
  const re = new RegExp(`(^|\n)\\s{${spaces}}`, "g")
  return str.replace(re, "$1")
}

const makeChildren = (str) =>
  str === ""
    ? []
    : str.split(/\n(?!\s)/).map(make1)

const make1 = (str = "") =>
{ const [ value, children ] = cut(str, "\n")
  return { value, children: makeChildren(outdent(children)) }
}

const data = `
todo list
  learn js
    hello world
    functions

shopping list
  costco
  berries


  mushrooms
procrastination list
`

const result =
  makeChildren(sanitize(data))

console.log(JSON.stringify(result, null, 2))
// [ { value: "todo list"
//   , children:
//       [ { value: "learn js"
//         , children:
//             [ { value: "hello world", children: [] }
//             , { value: "functions", children: [] }
//             ]
//         }
//       ]
//   }
// , { value: "shopping list"
//   , children:
//       [ { value: "costco", children: [] }
//       , { value: "berries", children: [] }
//       , { value: "mushrooms", children: [] }
//       ]
//   }
// , { value: "procrastination list", children: [] }
// ]

---

имеет для меня смысл!

Является ли программа "простой и понятной", потому что она имеет смысл для меня? Что если бы мы могли использовать объективных качеств для таких утверждений? @ tokafew420 уверен в своей программе, и поэтому я предлагаю этот объективный анализ.

Я изменил имена переменных на _n в каждой программе, чтобы мы могли легко идентифицировать и подсчитывать отдельные движущиеся части -

const TxtParser = _1 => { // 10 total variables; 4 mutations; 5 variable reassignments
  let _2 = []; // <-- mutates below but never reassigned; should be const
  let _3 = []; // <-- mutates below but never reassigned; should be const
  let _4 = {   // <-- reassigned below
    nbrSpaces: -1,
    children: _2 // <-- mutates below
  };
  let _5; // <-- reassigned below
  if (_1) {
    let _6 = _1.split("\n"); // <-- reassignment #1
    let _7 = _6.length;      // <-- reassignment #2
    if (_7) {
      let i;                 // <-- mutates; leaks variable out of `for` scope
      for (i = 0; i < _7; i++) {     // <-- mutation #1
        let _8 = _6[i].trim();       // <-- never reassigned, does not mutate; should be const
        let _9 = _6[i].search(/\S/); // <-- never reassigned, does not mutate; should be const
        if (_8) {
          let _10 = {                // <-- never reassigned, does not mutate; should be const
            line: _8,
            nbrSpaces: _9,
            children: []
          };
          if (_5 && _9 > _5.nbrSpaces) {
            _3.push(_4);         // <-- mutation #2
            _4 = _5;             // <-- reassignment #3
          } else {
            while (_9 <= _4.nbrSpaces) {
              _4 = _3.pop();     // <-- reassignment #4 AND mutation #3
            }
          }
          _4.children.push(_10); // <-- mutation #4
          _5 = _10;              // <-- reassignment #5
        }
      }
    }
  }
  return _2;
};

• наибольшее количество переменных в одной области: 10
• мутаций: 4
• переназначения переменных: 5
• строк реализации: 36
• многократно используемые функции: 0
• нуждается в дополнительном преобразовании для получения желаемого результата: да

Сравните это с декларативным функциональным подходом -

const sanitize = (_1 = "") => // 1 total variable; never mutates; never reassigned
  _1.trim().replace(/\n\s*\n/g, "\n")

const cut = (_1 = "", _2 = "") => // 3 total variables; never mutates; never reassigned
{ const _3 = _1.search(_2)
  return _3 === -1
    ? [ _1, "" ]
    : [ _1.substr(0, _3), _1.substr(_3 + 1) ]
}

const outdent = (_1 = "") => // 3 total variables; never mutates; never reassigned
{ const _2 = Math.max(0, _1.search(/\S/))
  const _3 = new RegExp(`(^|\n)\\s{${_2}}`, "g")
  return _1.replace(_3, "$1")
}

const makeChildren = (_1) => // 1 total variable; never mutates; never reassigned
  _1 === ""
    ? []
    : _1.split(/\n(?!\s)/).map(make1)

const make1 = (_1 = "") =>  // 3 total variables; never mutates; never reassigned
{ const [ _2, _3 ] = cut(_1, "\n")
  return { value: _2, children: makeChildren(outdent(_3)) }
}

• наибольшее количество переменных в одной области: 3
• мутации: 0
• переназначения переменных: 0
• строк реализации: 13
• многоразовые функции: 3 (sanitize, cut, outdent)
• нуждается в дополнительном преобразовании для получения желаемого результата: нет

почему эти вещи имеют значение?

Когда в одной области видимости есть 10 переменных, и все они могут измениться и переназначиться в любое время, для нашего мозга очень трудно отследить все движущиеся части. Эта программа большая и сложная для написания. Даже если мы получим правильный результат для одного входа, как мы узнаем, что наша программа подходит для других входов? Необходимо написать больше тестов, чтобы гарантировать правильное поведение, и из-за его 36-строчного поведения c его нельзя использовать в других частях программы.

Если сравнить это с низкой сложностью функциональная программа, у нас есть меньшие функции с четко определенной целью, которые легко писать, тестировать и обслуживать, а также повторно использовать в других частях нашей программы. Как вы можете видеть, переименование переменных в _1, _2 и _3 едва ли ухудшает читабельность, так как наш мозг легко отслеживает 3 вещи одновременно, и даже легче, когда мы знаем, что эти 3 вещи не являются мутированный или переназначенный.

Какое значение x в строке Y императивной программы? Из-за всех мутаций и переназначений в for - while, вложенных в l oop, можно только догадываться. Если ваш мозг не заменен компьютером, на этот вопрос трудно ответить почти для всех переменных и всех строк в этой программе, и поэтому я представляю, что это совсем не просто или просто.

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

/ 2cents

Answer 4

Это частичный ответ, но он может помочь вам построить ваш объект:

var text = `todo list
  learn js
    hello world
  other level
   deeper
shopping list
  costco
procrastination list`;

var paths = []; // this will store our path tree

parseText = () => {
    var lines = text.split("\n");
    var outputObject = {};

    var pathsStack = [];
    var previousSpaces = 0;

    lines.forEach( line => {
      //var line = lines[key];
      var spaces = line.match(/^\s*/)[0].length; // search 

      if (spaces === 0){ // reset path stack
        pathsStack = [line.trim()];
      } else if (spaces > previousSpaces) {
        pathsStack.push(line.trim());
      } else if (spaces === previousSpaces) {
        pathsStack.pop(); // remove last item
        pathsStack.push(line.trim());
      } else if (spaces < previousSpaces) {
        pathsStack.pop(); // remove last two items
        pathsStack.pop(); 
        pathsStack.push(line.trim());
      } 

      previousSpaces = spaces;

      paths.push(pathsStack.join("."));
    });
    console.log(paths);
    /* 
    this will output an array in the following form:
      0: "todo list"
      1: "todo list.learn js"
      2: "todo list.learn js.hello world"
      3: "todo list.other level"
      4: "todo list.other level.deeper"
      5: "shopping list"
      6: "shopping list.costco"
      7: "procrastination list"

    you can now iterate through this array and insert it into your target object.
    */
  }