Создание древовидной структуры из плоского массива в JavaScript (без использования ссылок на объекты)

Question

Я пытаюсь сгенерировать древовидную структуру в JavaScript из плоского массива.Обычно это было бы довольно простым предложением - просто сохраните массив «стек» со ссылками на объекты-предки текущей рабочей области, упорядоченные по глубине вложения - вставьте новый элемент в стек при входе на другой вложенный уровень и вытолкните его при выходеодин, заменив текущий рабочий элемент объектом, на который ссылается (новый) последний элемент массива.

К сожалению, для этого требуется возможность передачи по ссылке, чего нет в JavaScript (ну, нетЯ знаю, каким образом я могу использовать эту проблему.)

Чтобы дать немного фона, я пытаюсь превратить произвольно длинную / сложную строку, содержащую вложенный XML-стиль (но не XML, поэтому вместо него нельзя использовать синтаксический анализатор XML) Маркеры в структуру, аналогичную приведенной ниже:

Ожидаемый ввод:

[
    "<token>",
    "<my non compliant token>",
    "some text at this level",
    "<some other token>",
    "some more text",
    "<yet another token>",
    "more text",
    "</yet another token>",
    "blah!",
    "</some other token>",
    "</token>",
    "more text"
]

Ожидаемый результат

[
    {
        "token": "<token>",
        "children": [
            {
                "token": "<my non compliant token>",
                "children": [
                    "some text at this level",
                    {
                        "token": "<some other token>",
                        "children": [
                            "some more text",
                            {
                                "token": "<yet another token>",
                                "children": [ "more text" ]
                            },
                            "blah!"
                        ]
                    }
                ]
            }
        ]
    },
    "more text"
]

Чтобы уточнить - я не после всего алгоритма (но мне было бы интересно, если уВы хотите предоставить свою реализацию) - просто хороший метод для поддержания текущей позиции в выводимом дереве (или совершенно другой / лучший способ генерации объектов дерева!) Не слишком увлекайтесь тем, как работают токены - онине XML, и для целей упражнения можно было бы отформатировать его совершенно по-разному.

Любая информация будет принята с благодарностью!

Answer 1

Ваши строки выглядят легко для анализа. Я думаю, я бы сделал что-то вроде этого:

var stack = [];
var array = [];
for (var i in strings) {
   var s = strings[i];
   if (s.indexOf("</") == 0) {
      array = stack.pop();
   } else if (s.indexOf("<") == 0) {
      var obj = {token: s, children: []};
      array.push(obj);
      stack.push(array);
      array = obj.children;
   } else {
      array.push(s);
   }
}

Answer 2

Идея # 1

Вот ответ, который вы, вероятно, не ожидали.

Глядя на ваш ожидаемый результат, я подумал, проще ли просто сгенерировать JSON, а затем оценить его, когда выготовоНет ссылок вообще.

Проходя через плоский массив, вы в основном выполняете три операции:

1. Вы добавляете больше данных к текущему объекту
2. Вы закрываете текущий объект
3. Вы создаете новый дочерний объект

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

Idea # 2

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

Это будет выглядеть примерно такэто:

function ParseRawData(rawData)
{
    var parentScopeArray = [];   // main parent scope of objects

    function processTag(x)
    {
        // you can access parentScopeArray directly here and
        // and be accessing it by reference
    }

    // other code or local functions here

}

Идея # 3

Если вы хотите передать массив в функцию и изменить мастер-копию (возможно, причина, по которой вы думаете о передаче по ссылке),шаблон проектирования javascript должен передавать массив и возвращать измененный массив, заменяя весь исходный массив измененным, который возвращается.