解析列表并打印所有最终路径

Question

给定的行有不同的缩进

orange
 blue
  yellow
  black
  white
 green

打印所有最终路径。

预期输出

orange/blue/yellow
orange/blue/black
orange/blue/white
orange/green

如何解析所有行（非二叉树）以打印最终（完整）路径？

Answer 1

该算法将使用堆栈：

保留一堆对，其中每对包含一个（部分）路径及其最后部分的缩进。堆栈中的条目总是通过缩进增加。堆栈开始为空。

对于输入的每一行，确定其缩进。只要堆栈上有等于或大于的缩进，就从堆栈中删除这些对。然后获取堆栈顶部的路径，将当前行附加到该路径（没有缩进，由 / 分隔），将其与新的缩进配对，并将其推入堆栈。输出该路径并为下一个输入行重复该过程。

这是 JavaScript 中的一个实现：

function getIndent(s) {
    return s.search(/\S/); // Index of first non-white-space character
}

function getPaths(text) {
    let stack = [];
    let paths = [];
    for (let line of text.split("\n")) {
        let indent = getIndent(line);
        while (stack.length > 0 && indent <= stack.at(-1).indent) {
            stack.pop();
        }
        let path = (stack.length > 0 ? stack.at(-1).path + "/" : "") + line.trim();
        stack.push({path, indent});
        paths.push(path);
    }
    return paths;
}

// Sample input
let text = 
`orange
 blue
  yellow
  black
  white
 green`;
 
for (let path of getPaths(text)) {
    console.log(path);
}

解析列表并打印所有最终路径

Parse list and print all final paths

tree

traversal