首页 > 试题广场 >

设计一个函数2

[编程题]设计一个函数2
  • 热度指数:895 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
设计一个函数,传入一个可序列化为树结构的字符串,将含有多个子节点的节点以数组的形式输出。

输入描述:
{ 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' }] } } ] }


输出描述:
数组
输出规范
1)数组应被左右中括号括起;
2)数组的元素间由','相隔;
3)各节点在数组中的顺序应和其在输入中出现的次序一致;
4)节点名保证为不超过30个字符的字符串,仅含大小写字母、数字及下划线,输出时应用双引号括起;
5)输出的字符串不应有多余的空格。
示例1

输入

{ 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' }] } } ] }

输出

["root","second_child","third_child"]
""""
字符串匹配和递归
{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)))

编辑于 2019-07-14 20:25:01 回复(0)
//直接输入输出即可
#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<<"\""<<",";
    }
}

发表于 2020-03-15 08:06:45 回复(1)
#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;
}

发表于 2020-01-08 11:19:54 回复(0)
用C++写的,最后结果说是86.67%,可能发生数组越界,但不提示用例了,希望会的人可以指导一下~
#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);
}

发表于 2019-11-09 15:52:33 回复(1)
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;
}
求大佬指教
发表于 2020-09-29 11:48:31 回复(0)
// 找[, [前最后一对‘’即为输出结点
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"]
    }
} 

发表于 2020-09-15 02:58:02 回复(0)

题目描述

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

看完题目后,本质上就是让我们自己弄个程序来解析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();//输出结果
    }
}
发表于 2020-03-21 21:27:43 回复(1)
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main()
{
    string str;
    getline(cin, str);
    vector<string> vec;
    int j = 0;
    for(int i = 0; i < str.size(); ++i)
    {
        if(str[i] == '\'')
        {
            for(j = i + 1;j < str.size(); ++j)
            {
                if(str[j] == '\'')
                {
                    if(str.substr(j + 1, 9) == ", next: [" || str.substr(j + 1, 10) == " , next: [")
                    {
                        string s = str.substr(i + 1, j - i - 1);
                        vec.push_back(s);
                        break;
                    }
                    else
                    {
                        break;
                    }
                }
            }
            i = j;
        }
    }
    cout << "[";
    for(int i = 0; i < vec.size(); ++i)
    {
        if(i == vec.size() - 1)
            cout << "\"" << vec[vec.size() - 1] << "\"";
        else
            cout << "\"" << vec[i] << "\"" << ",";
    }
    cout << "]";
    return 0;
}
发表于 2019-12-27 12:56:39 回复(0)
//这是js的解法

while(line = readline()){
    var lines = line.trim();
    lines = "c=" +lines;
    var object = eval(lines);
    var list = [];

    function find(obj){
       if(obj.next){
           if(!(obj.next.length)){
               find(obj.next)
           }else{
              list.push(obj.node);
              for(var i =0;i< obj.next.length;i++){
                  find(obj.next[i]);
              }
           }
       }
    }

     find(object);
     var a = "[";
     var len = list.length;
    if(len == 0){
        a = "[]";
    }else{        
        for(var i = 0;i<len;i++){
             if(i==len-1){
                a=a+'"'+list[i]+'"'+"]"
             }else{
                a =a+'"'+list[i]+'"'+',';
             }
         }
    }
     console.log(a);
}

发表于 2019-09-25 23:37:42 回复(0)
这种题C++写起来是真的麻烦
发表于 2019-09-12 11:22:03 回复(0)
"""
不知道哪错了,一直是93.33%的通过率,找不到问题在哪,求各位大神指明道路!
"""
import re

def find(s, result):
    if "[" not in s:
        return

    node = re.search(r"'[a-z_0-9]*'", s, re.I)
    _, start = node.span()
    judge = re.match(r",next:\[", s[start:], re.I)
    if judge:
        result.append('"' + node.group()[1:-1] + '"')
    find(s[start:], result)
        

if __name__ == "__main__":
    s = input().replace(" ", "")
    result = []
    find(s, result)
    print('[{}]'.format(','.join(result)))
发表于 2019-09-07 21:35:56 回复(0)