ZOJ 3826 Hierarchical Notation 模拟

ZOJ 3826 Hierarchical Notation 模拟

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

模拟: 语法的分析

hash一切Key建设规划,对于记录在几个地点的每个节点原始的字符串开始输出。

。。

对每一个询问沿图走就能够了。

。。


Hierarchical Notation



Time Limit: 2 Seconds      
Memory Limit: 131072 KB


In Marjar University, students in College of Computer Science will learn EON (Edward Object Notation), which is a hierarchical data format that uses human-readable text to transmit data objects consisting of attribute-value pairs. The EON was invented by Edward, the headmaster of Marjar University.

The EON format is a list of key-value pairs separated by comma “,”, enclosed by a couple of braces “{” and “}”. Each key-value pair has the form of “<key>”:”<value>”. <key> is a string consists of alphabets and digits. <value> can be either a string with the same format of <key>, or a nested EON.

To retrieve the data from an EON text, we can search it by using a key. Of course, the key can be in a nested form because the value may be still an EON. In this case, we will use dot “.” to separate different hierarchies of the key.

For example, here is an EON text:

{“headmaster”:”Edward”,”students”:{“student01″:”Alice”,”student02″:”Bob”}}

  • For the key “headmaster”, the value is “Edward”.
  • For the key “students”, the value is {“student01″:”Alice”,”student02″:”Bob”}.
  • For the key “students”.”student01″, the value is “Alice”.

As a student in Marjar University, you are doing your homework now. Please write a program to parse a line of EON and respond to several queries on the EON.

Input

There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

The first line contains an EON text. The number of colons “:” in the string will not exceed 10000 and the length of each key and non-EON value will not exceed 20.

The next line contains an integer Q (0 <= Q <= 1000) indicating the number of queries. Then followed by Q lines, each line is a key for query. The querying keys are in correct format, but some of them may not exist in the EON text.

The length of each hierarchy of the querying keys will not exceed 20, while the total length of each querying key is not specified. It is guaranteed that the total size of input data will not exceed 10 MB.

Output

For each test case, output Q lines of values corresponding to the queries. If a key does not exist in the EON text, output “Error!” instead (without quotes).

Sample Input

1
{"hm":"Edward","stu":{"stu01":"Alice","stu02":"Bob"}}
4
"hm"
"stu"
"stu"."stu01"
"students"

Sample Output

"Edward"
{"stu01":"Alice","stu02":"Bob"}
"Alice"
Error!

Author: 
LU, Yi


Source: 
The 2014 ACM-ICPC Asia Mudanjiang Regional Contest

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <stack>

using namespace std;

typedef long long int LL;

LL hash(char* str)
{
    LL ret=0;
    int len=strlen(str);
    for(int i=0;i<len;i++)
    {
        ret=ret*123+(LL)(str[i]-'0');
    }
    return ret;
}

map<LL,int> mp;
stack<int> stk;

char str[400007],que[400007];
bool graph[10000][10000];
int stpt[400007];

void init()
{
    mp.clear(); while(!stk.empty()) stk.pop();
    memset(graph,false,sizeof(graph));
}

int main()
{
    int T_T;
    scanf("%d",&T_T);
    while(T_T--)
    {
        init();
        scanf("%s",str);
        int len=strlen(str);
        int word=0;
        bool readname=false;
        char name[50]; int na;
        for(int i=0;i<len;i++)
        {
            if(str[i]=='{') stk.push(word);
            else if(str[i]=='}') stk.pop();
            else if(str[i]=='"')
            {
                if(readname==false)
                {
                    readname=true;
                    memset(name,0,sizeof(name)); na=0;
                }
                else if(readname==true)
                {
                    readname=false;
                    LL id=hash(name);
                    word++;
                    mp[id]=word;
                    stpt[mp[id]]=i+1;
                    graph[stk.top()][word]=true;
                }
            }
            else if(str[i]==':')
            {
                if(str[i+1]=='{') continue;
                else if(str[i+1]=='"')
                {
                    i++;
                    while(str[i+1]!='"')
                        i++;
                    i++;
                }
            }
            else if(readname==true)
            {
                name[na++]=str[i];
            }
        }
        int m;
        scanf("%d",&m);
        while(m--)
        {
            scanf("%s",que);
            int len2=strlen(que);
            bool flag=true;
            na=0; int p=0;
            readname=false;
            for(int i=0;i<len2&&flag;i++)
            {
                if(que[i]=='"')
                {
                    if(readname==false)
                    {
                        na=0; memset(name,0,sizeof(name));
                        readname=true;
                    }
                    else if(readname==true)
                    {
                        readname=false;
                        LL id=hash(name);
                        if(graph[p][mp[id]]==true)
                        {
                            p=mp[id];
                        }
                        else flag=false;
                    }
                }
                else if(que[i]=='.') continue;
                else name[na++]=que[i];
            }
            if(flag==false) puts("Error!");
            else
            {
                char cc=str[stpt[p]+1];
                int dep=0;
                if(cc=='{') cc='}';
                int ii=stpt[p]+1;
                if(cc=='"') { ii++; putchar('"'); }
                while(true)
                {
                    if(cc=='}')
                    {
                        if(str[ii]=='{') dep++;
                        if(str[ii]=='}') dep--;
                        if(dep==0) break;
                    }
                    else if(cc=='"')
                    {
                        if(str[ii]=='"') break;
                    }
                    putchar(str[ii]); ii++;
                }
                putchar(cc);
                putchar(10);
            }
        }
    }
    return 0;
}

版权声明:本文博客原创文章,博客,未经同意,不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117623.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 卷积核与特征提取_卷积层特征各层如何保存

    卷积核与特征提取_卷积层特征各层如何保存线性滤波与卷积的基本概念线性滤波可以说是图像处理最基本的方法,它可以允许我们对图像进行处理,产生很多不同的效果。做法很简单。首先,我们有一个二维的滤波器矩阵(有个高大上的名字叫卷积核)和一个要处理的

  • 联想服务器怎么拆硬盘,联想ThinkStation P900工作站高清拆解[通俗易懂]

    联想服务器怎么拆硬盘,联想ThinkStation P900工作站高清拆解[通俗易懂]【IT168厂商动态】联想不久前推出了全新一代ThinkStationP系列工作站家族,颠覆以往命名,启用以“P”开头的全新命名规则,包括从入门级到旗舰级应用的ThinkStationP300、ThinkStationP500、ThinkStationP700和ThinkStationP900四款产品,而今天我们就对号称“史上最强工作站”的ThinkStationP900进行了拆解。联…

  • DataGrip 2021.12.12 激活码【2021免费激活】

    (DataGrip 2021.12.12 激活码)这是一篇idea技术相关文章,由全栈君为大家提供,主要知识点是关于2021JetBrains全家桶永久激活码的内容IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html0BXA05X8YC-eyJsa…

  • 播放ipod歌曲

    播放ipod歌曲

  • Android ListView等列表设置空布局

    Android ListView等列表设置空布局在Android平台上,listView是特别常用的组件之一,我们在向用户展示列表数据时,通常要考虑:列表有数据和无数据空的状态,因为网络环境各异,难免刷新失败什么的;在此之前我是使用ViewStub来实现,通过判断listview列表数据是否为空来设置ViewStub的隐藏和显示,或者设置lIstview的显示或隐藏;但是,对ViewStub不是特别的了解,把控不好,只是控

  • 涂鸦模组开发光照传感器的作用_光学模组

    涂鸦模组开发光照传感器的作用_光学模组涂鸦模组开发光照传感器(OPT3006)概述涂鸦智能系统框架设计OPT3006超薄环境光传感器TYZS5模组特点PCB绘制涂鸦零代码开发涂鸦模组开发文章概述亮度传感器是一种常用的智能检测设备,主要利用亮度集成传感器,实时检测环境明暗的亮度数据。它不仅仅适用于智能家居体系,同样被广泛应用于场景中,例如办公楼、酒店、公寓、学校、医院、养老院、商场、餐厅、银行、仓库、街道等。根据外界环境光线的明暗,实现与其它智能设备的联动;还可通过设定延时功能,避免光线瞬间变化造成干扰。在此,分析并选取合适的平台、传

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号