Как составить дерево из вложенных значений в скобки?

Question

[MishaXXL]

Как составить дерево из вложенных значений?
(1 (20 (400 5 60 (700) 108 (90)) 3))
По какому принципу создается вложенность при обходе строки с учётом вложенности путем скобок?

Answer 1

[Alexandroppolus]

конкретно в данном случае (только числа) можно воспользоваться парсингом JSON, предварительно доработав напильником строку

const result = JSON.parse(
  '(1 (20 (400 5 60 (700) 108 (90)) 3))'
  .replaceAll('(', '[')
  .replaceAll(')', ']')
  .replace(/(\d|\])(?=\s+\d|\s*\[)/g, '$&,'));

----
ну а если по-честному, то надо обходить строку, и либо рекурсией, либо со стеком.

Примерно так:

код внутри

function getTree(str) {
    const tokens = str.match(/\d+|[()]/g);

    const stack = [];
    let currentArr = null;

    for(let i = 0; i < tokens.length; ++i) {
        const token = tokens[i];
        if (token === ')') {
            if (!stack.length) {
                return currentArr;
            }
            currentArr = stack.pop();
        } else if (token === '(') {
            const newArr = [];
            if (currentArr) {
                currentArr.push(newArr);
                stack.push(currentArr);
            }
            currentArr = newArr;
        } else {
            if (currentArr) {
                currentArr.push(parseInt(token));
            }
        }
    }
    return currentArr;
}

const result = getTree('(1 (20 (400 5 60 (700) 108 (90)) 3))');

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

Comments

[MishaXXL]

Если можно )
Я не совсем понял, как идти в ширину
Т.е. перебрать все значения в одну линию получилось, а как разбивать их в ширину в подмассивы и как после их вообще вывести так же древовидно, не понял

[Alexandroppolus]

MishaXXL, дополнил ответ

[MishaXXL]

Alexandroppolus, пробую, какая-то сложная логика, думал есть алгоритм простой )

[Alexandroppolus]

MishaXXL, да куда уж проще-то?)