设计一个函数2

题目描述

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

看完题目后，本质上就是让我们自己弄个程序来解析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();//输出结果
    }
}