设计一个函数2

""""
字符串匹配和递归
{node: 'root', next:
    [{node: 'second_root'},
     {node: 'second_child', next:
         [{node: 'second_child_1', next:
             {node: 'second_child_1_1'}
           },
          {node: 'second_child_2'}
          ]
      },
     {node: 'third_root', next:
         {node: 'third_child', next:
             [{node: 'third_child_1', next:
                 {node: 'third_child_1_1'}
               },
              {node: 'third_child_2'}
              ]
          }
      }
     ]
 }
"""
import sys


def find_node(s, ans, dic):
    node = s[s.index("'") + 1:s.index("'") + 1 + s[s.index("'") + 1:].index("'")].strip()
    ans.append(node)  # 添加node名到ans列表中
    dic[node] = 0  # node的子节点
    if '{' not in s:  # 没有子节点
        return
    x = s.index('{')  # 至少一个子节点，记录递归的起始位置 x+1
    stack = []  # 栈用于符号配对，此题标准格式不需要验证符号是否匹配，只记录是否为空
    y = x
    for y in range(x, len(s)):
        if s[y] == '{':
            if not stack:
                x = y  # 记录递归的起始位置
            stack.append(s[y])
        elif s[y] == '}':
            stack.pop()
            if not stack:  # 栈空则，dic[node]加一，且对字符串 s[x + 1:y] 递归
                dic[node] += 1
                find_node(s[x + 1:y], ans, dic)


if __name__ == "__main__":
    # sys.stdin = open("input.txt", "r")
    s = input().strip()
    ans = []  # 按输入顺序记录所有节点
    dic = {}  # 记录node有几个子节点
    find_node(s[1:-1], ans, dic)
    res = []  # 符合多个子节点要求的所有节点
    flag = False
    for c in ans:
        if dic[c] >= 2:
            res.append('"' + c + '"')
    print("[{0}]".format(','.join(res)))

	

//直接输入输出即可
#include<iostream>
(720)#include<vector>
using namespace std;
int main()
{
    char ch;
    string name;
    vector<string> v;
    while((ch=getchar())!='\n')
    {
        if(ch=='\'')
        {
            name="";
            while((ch=getchar())!='\'')
                name+=ch;
        }
        if(ch=='[')
            v.push_back(name);
    }
    cout<<"[";
    if(v.size()==0)
    {
        cout<<"]";
        return 0;
    }
    for(auto it=v.begin();it!=v.end();it++)
    {
        if(it==v.end()-1)
            cout<<"\""<<*it<<"\""<<"]";
        else
            cout<<"\""<<*it<<"\""<<",";
    }
}

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

int main(){
    string s, t="";
    getline(cin, s);
    for(int i=0;i<s.length();i++)
        if(s[i]!=' ')
            t += s[i];
    string p = "next:[{";
    int k = 0;
    vector<string> v;
    while((k=t.find(p, k)) != string::npos){
        int r=k-1;
        while(t[r]!='\'')
            r--;
        int l=r-1;
        while(t[l]!='\'')
            l--;
        v.push_back(t.substr(l+1, r-l-1));
        k++;
    }
    cout<<"[";
    for(int i=0;i<v.size();i++){
        if(i==0)
            cout<<"\""<<v[0]<<"\"";
        else
            cout<<",\""<<v[i]<<"\"";
    }
    cout<<"]"<<endl; 
    return 0;
}

#include <iostream>
#include <queue>
#include <string>
using namespace std;
void function2(string str) {
	queue<char>q;
	for (int i = 0; i < str.size() - 6; i++) {
		if (str[i] == 'n'&&str[i + 1] == 'e'&&str[i + 2] == 'x'&&str[i + 3] == 't'&&str[i + 4] == ':'&&str[i + 6] == '[') {
			i = i - 5;
			while (str[i] != '\'')
				i--;
			q.push('"');
			while (str[++i] != '\'')
				q.push(str[i]);
			q.push('"');
			q.push(',');
			i += 9;
		}
	}
	cout << "[";
	while (q.size() != 1){
		cout << q.front();
		q.pop();
	}
	cout << "]";
}

int main()
{
	string s;
	getline(cin, s);
	function2(s);
}

function findMultiChildren(obj) {
    const res = [];
 
    if (obj.next && Array.isArray(obj.next)) {
        if (obj.next.length > 1) {
            res.push(obj.node);
        }
        for (let i = 0; i < obj.next.length; i++) {
            res.push(...findMultiChildren(obj.next[i]));
        }
    } else if (obj.next && typeof obj.next === 'object') {
        res.push(...findMultiChildren(obj.next));
    }
    return res;
}

// 找[, [前最后一对‘’即为输出结点
import java.util.*;

public class Main {
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        String[] arr = line.split("\\[");
        ArrayList<String> list = new ArrayList<>();
        for (int i = 0; i < arr.length-1; i++) {
        	int to = arr[i].lastIndexOf('\'');
        	int from = arr[i].substring(0, to).lastIndexOf('\'');
        	list.add(arr[i].substring(from + 1, to));
        }
        System.out.print("[");
        for (int i = 0; i < list.size(); i++) {
        	System.out.printf("\"%s\"", list.get(i));
        	if(i != list.size()-1)
        		System.out.printf(",");
        }
        System.out.println("]"); // ["root","second_child","third_child"]
    }
} 

题目描述

• 设计一个函数，传入一个可序列化为树结构的字符串，将含有多个子节点的节点以数组的形式输出。

看完题目后，本质上就是让我们自己弄个程序来解析json格式数据，突然满脑子都在呼喊编译原理，那我们就尝试用编译原理解决一波吧。

词法部分

首先数据格式只是json一个小子集，涉及词法简单，不需要搞那么复杂，为了便于处理设计以下变量和函数

• int pos记录编译器扫描到的位置
• void scan_brace()将pos扫过前方空格换行制表符
• boolean scan_char(char c)扫描前方字符c，如果不是c返回false
• boolean scan_str(String str)扫描前方字符串，如果不是str返回false
• String get_str()扫描并获取一个前方字符串（'字符串')
• char preview()查看当前字符

语法部分

不太规范的语法制导翻译

节点 -> { node : 字符串(记录字符串) 子节点(为字符串设置子节点数量) } 返回：无

子节点 -> 空 返回：0

子节点 -> , next : [ 节点 节点列表 ] (返回：节点列表子节点数+1) 或{ 节点 } (返回：1)

节点列表 ->空 返回 1

节点列表 -> , 节点 节点列表 返回：节点列表子节点数+1

其实就三个产生式，写起来不算麻烦，但是太久没写了熟练度有所降低，犯了好多低级错误。

代码

import java.util.*;
public class Main{
    //缓冲区操作部分
    static char[]buffer;
    static int pos;
    static void read_in(){
        Scanner scan=new Scanner(System.in);
        String str="";
        while(scan.hasNext())str+=scan.nextLine();
        buffer=str.toCharArray();
        pos=0;
    }
    static void scan_brace(){
        while(buffer[pos]==' '||buffer[pos]=='\t'||buffer[pos]=='\n')pos++;
    }
    static boolean scan_char(char c){
        scan_brace();
        return buffer[pos++]==c;
    }
    static boolean scan_str(String str){
        scan_brace();
        char[]crr=str.toCharArray();
        for(int i=0;i<crr.length;i++){
            if(crr[i]!=buffer[pos++])return false;
        }
        return true;
    }
    static char preview(){
        scan_brace();
        return buffer[pos];
    }
    static String get_str(){
        scan_brace();
        scan_char('\'');
        String res="";
        while(preview()!='\'')res+=buffer[pos++];
        pos++;
        return res;
    }
    //数据管理部分
    static Mapmap=new HashMap();//记录节点名称出现的次数
    static ArrayListarr=new ArrayList();//按次记录出现的节点名称
    static void add(String str){
        arr.add(str);
    }
    static void put(String str,int val){
        map.put(str,val);
    }
    static void print(){
        int size=arr.size();
        boolean first=true;
        System.out.print("[");
        for(int i=0;i<size;i++){
            String temp=arr.get(i);
            if(map.get(temp)>1){
                if(first){
                    System.out.print("\""+temp+"\"");
                    first=false;
                }
                else System.out.print(",\""+temp+"\"");
            }
        }
        System.out.println("]");
    }
    //编译部分
    static void node(){
        scan_char('{');
        scan_str("node");
        scan_char(':');
        String name=get_str();
        add(name);
        int num=subnode();
        put(name,num);
        scan_char('}');
    }
    static int subnode(){
        if(preview()==','){
            scan_char(',');
            scan_str("next");
            scan_char(':');
            if(preview()=='['){
                scan_char('[');
                node();
                int num=list();
                scan_char(']');
                return num+1;
            }
            else{
                node();
                return 1;
            }
        }
        else return 0;
    }
    static int list(){
        if(preview()==','){
            scan_char(',');
            node();
            return list()+1;
        }
        else return 0;
    }
    public static void main(String args[]){
        read_in();//读入数据并初始化
        node();//编译
        print();//输出结果
    }
}