题目描述

在一个博客网站上，每篇博客都有评论。每一条评论都是一个非空的英文字母字符串，并且评论之间具有树状结构，除了根评论外，每个评论都有一个父评论。当评论保存时，使用以下格式进行存储：

1. 首先是评论的内容；
2. 然后是回复当前评论的数量；
3. 最后是当前评论的所有子评论（子评论使用相同的格式嵌套存储）。

任务是将这种格式的评论转换为另一种格式：

1. 首先打印评论嵌套的最大深度。
2. 然后打印n行，第i行对应嵌套级别为i的评论（根评论的嵌套级别为1）。对于第i行，嵌套级别为i的评论按照输入中的顺序打印，用空格分隔。

思路

要解决这个问题，需要解析输入的字符串，构建评论的树状结构，并记录每个评论所在的深度。具体步骤如下：

1. 解析输入字符串：将输入字符串按照逗号分割成一个数组，逐个处理。
2. 使用栈进行遍历：利用栈来跟踪当前处理的评论的父级信息，包括剩余的子评论数量和当前的深度。
3. 记录每个评论的深度：在遍历过程中，记录每个评论所在的深度，并将其添加到对应深度的列表中。
4. 处理多个根评论：确保程序能够处理多个根评论，即多个评论没有共同的父评论。
5. 更新最大深度：维护一个变量记录最大深度。
6. 输出结果：根据记录的深度信息输出最大深度及各层的评论。

cpp

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin >> s;
    // 将输入按逗号分割
    vector<string> tokens;
    int n = s.size();
    string token = "";
    for(char c : s){
        if(c == ','){
            tokens.push_back(token);
            token = "";
        }
        else{
            token += c;
        }
    }
    tokens.push_back(token); // 添加最后一个token

    // 用于存储每个深度的评论
    vector<vector<string>> levels;
    int max_depth = 0;

    // 栈中存储 pair<剩余子评论数, 当前深度>
    // 初始化栈为空，处理多个根评论
    stack<pair<int, int>> stk;

    int i = 0;
    while(i < tokens.size()){
        // 如果栈为空，表示处理一个新的根评论
        if(stk.empty()){
            // 根评论的深度为1
            int current_depth = 1;
            // 更新最大深度
            if(current_depth > max_depth){
                max_depth = current_depth;
                levels.emplace_back();
            }
            // 确保levels的大小
            if(current_depth > levels.size()){
                levels.resize(current_depth);
            }
            // 当前评论内容
            string content = tokens[i++];
            // 当前评论的回复数量
            int cnt = stoi(tokens[i++]);
            // 添加到对应深度
            levels[current_depth-1].push_back(content);
            // 如果有子评论，入栈
            if(cnt > 0){
                stk.push({cnt, current_depth});
            }
            continue;
        }

        // 当前的父节点信息
        while(!stk.empty() && stk.top().first == 0){
            stk.pop();
        }
        if(stk.empty()){
            continue; // 可能有多个根评论
        }
        // 当前深度
        int current_depth = stk.top().second + 1;
        // 更新最大深度
        if(current_depth > max_depth){
            max_depth = current_depth;
            levels.emplace_back();
        }
        // 确保levels的大小
        if(current_depth > levels.size()){
            levels.resize(current_depth);
        }
        // 当前评论内容
        string content = tokens[i++];
        // 当前评论的回复数量
        int cnt = stoi(tokens[i++]);
        // 添加到对应深度
        levels[current_depth-1].push_back(content);
        // 减少父节点的剩余子评论数
        stk.top().first -=1;
        // 如果有子评论，入栈
        if(cnt > 0){
            stk.push({cnt, current_depth});
        }
    }

    // 输出
    cout << max_depth << "\n";
    for(int d=0; d<max_depth; d++){
        for(int j=0; j<levels[d].size(); j++){
            if(j > 0) cout << ' ';
            cout << levels[d][j];
        }
        cout << "\n";
    }
}

python

import sys

def main():
    s = sys.stdin.read().strip()
    tokens = s.split(',')

    levels = []
    max_depth = 0
    stack = []  # 栈中存储 (剩余子评论数, 当前深度)

    i = 0
    while i < len(tokens):
        # 如果栈为空，处理新的根评论
        if not stack:
            current_depth = 1
            content = tokens[i]
            cnt = int(tokens[i+1])
            if current_depth > max_depth:
                max_depth = current_depth
                levels.append([])
            if current_depth > len(levels):
                levels.append([])
            levels[current_depth-1].append(content)
            if cnt > 0:
                stack.append([cnt, current_depth])
            i += 2
            continue

        # 更新栈，找到当前应该处理的父评论
        while stack and stack[-1][0] == 0:
            stack.pop()
        if not stack:
            continue
        # 当前深度
        current_depth = stack[-1][1] +1
        # 当前评论内容
        content = tokens[i]
        cnt = int(tokens[i+1])
        if current_depth > max_depth:
            max_depth = current_depth
            levels.append([])
        if current_depth > len(levels):
            levels.append([])
        levels[current_depth-1].append(content)
        # 减少父节点的剩余子评论数
        stack[-1][0] -=1
        # 如果有子评论，入栈
        if cnt >0:
            stack.append([cnt, current_depth])
        i +=2

    # 输出
    print(max_depth)
    for level in levels:
        print(' '.join(level))

if __name__ == "__main__":
    main()

java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine().trim();
        String[] tokens = s.split(",");

        List<List<String>> levels = new ArrayList<>();
        int max_depth = 0;

        // 栈中存储剩余子评论数和当前深度
        Deque<int[]> stack = new ArrayDeque<>();

        int i =0;
        while(i < tokens.length){
            // 如果栈为空，处理新的根评论
            if(stack.isEmpty()){
                int current_depth =1;
                String content = tokens[i++];
                int cnt = Integer.parseInt(tokens[i++]);
                if(current_depth > max_depth){
                    max_depth = current_depth;
                    levels.add(new ArrayList<>());
                }
                while(levels.size() < current_depth){
                    levels.add(new ArrayList<>());
                }
                levels.get(current_depth-1).add(content);
                if(cnt >0){
                    stack.push(new int[]{cnt, current_depth});
                }
                continue;
            }

            // 更新栈，找到当前应该处理的父评论
            while(!stack.isEmpty() && stack.peek()[0] ==0){
                stack.pop();
            }
            if(stack.isEmpty()){
                continue;
            }

            // 当前深度
            int current_depth = stack.peek()[1] +1;
            String content = tokens[i++];
            int cnt = Integer.parseInt(tokens[i++]);
            if(current_depth > max_depth){
                max_depth = current_depth;
                levels.add(new ArrayList<>());
            }
            while(levels.size() < current_depth){
                levels.add(new ArrayList<>());
            }
            levels.get(current_depth-1).add(content);
            // 减少父节点的剩余子评论数
            stack.peek()[0] -=1;
            // 如果有子评论，入栈
            if(cnt >0){
                stack.push(new int[]{cnt, current_depth});
            }
        }

        // 输出
        StringBuilder sb = new StringBuilder();
        sb.append(max_depth).append("\n");
        for(List<String> level : levels){
            sb.append(String.join(" ", level)).append("\n");
        }
        System.out.print(sb.toString());
    }
}

题目内容

在一个博客网站上，每篇博客都有评论。

每一条评论都是一个非空英文字母字符串。

评论具有树状结构，除了根评论外，每个评论都有一个父评论。

当评论保存时，使用以下格式：

首先是评论的内容； 然后是回复当前评论的数量。 最后是当前评论的所有了评论。(子评论使用相同的格式嵌套存储) 所有元素之间都用单个逗号分隔。

例如，如果评论如下：

第一条评论是"helo,2,ok,0,bye,0"，第二条评论是"test,0"，第三条评论是"one,1,two,1,a,0"。

所有评论被保存成"hello,2,ok,0.bye,0,test,0,one,1,two,1,a,0"。

对于上述格式的评论，请以另外一种格式打印：

首先打印评论嵌套的最大深度。 然后是打印n行，第 i (1 ≤ i ≤ n) 行对应于嵌套级别为 i 的评论 (根评论的嵌套级别为1)。 对于第 i 行，嵌套级别为的评论按照它们出现的顺序打印，用空格分隔开。

输入描述

一行评论。由英文字母、数字和英文逗号组成。

保证每个评论都是由英文字符组成的非空字符串。

每个评论的数量都是整数 (至少由一个数字组成)。

整个字符串的长度不超过10^6。

给定的评论结构保证是合法的

输出描述

按照给定的格式打印评论。对于每一级嵌套，评论应该按照输入中的顺序打印

样例1

输入

hello,2,ok,0,bye,0,test,0,one,1,two,1,a,0

输出

3
hello test one
ok bye two
a

说明

如题目描述中图所示，最大嵌套级别为3，嵌套级别为1的评论是"hello test one"，嵌套级别为2的评论是"ok bye two"，嵌套级别为3的评论为”a"”。

样例2

输入

A,5,A,0,a,0,A,0,a,0,A,0

输出

2
A
A a A a A

说明

如下图所示，最大嵌套级别为2，嵌套级别为1的评论是"A”，嵌套级别为2的评论是"A a A a A"

样例3

输入

A,3,B,2,C,0,D,1,E,0,F,1,G,0,H,1,I,1,J,0,K,1,L,0,M,2,N,0,O,1,P,0

输出

4
A K M
B F H L N O
C D G I P
E J

说明

如下图所示