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)


相关推荐

  • 好用的tracker服务器_tracker服务器地址

    好用的tracker服务器_tracker服务器地址BTTracker是一款小巧便捷的BT种子制作辅助小工具,功能强大,并且可以通过导入导出数据片段来批量添加项目,当然这里主要说的是Tracker服务器列表——announce-list,但是就批量增添Tracker来说还是不够方便。然后终于找到个专门针对Tracker的编辑工具,可以将下边的TorrentTracer列表写入TrackerEditor程序同目录下的add_trackers.tx…

  • px2rem配置_px和rem转换器

    px2rem配置_px和rem转换器安装px2rem后,再使用px上有些不同,大家可以参考px2rem官方介绍,下面简单介绍一下。直接写px,编译后会直接转化成rem—-除开下面两种情况,其他长度用这个在px后面添加/*no*/,不会转化px,会原样输出。—一般border需用这个在px后面添加/*px*/,会根据dpr的不同,生成三套代码。—-一般字体需用这个 …

    2022年10月23日
  • 微信电脑版打不开怎么办?电脑版微信打不开的解决方案_wechatwin.dll文件缺失怎么解决

    微信电脑版打不开怎么办?电脑版微信打不开的解决方案_wechatwin.dll文件缺失怎么解决微信现在除了是日常的交流工具,基本上办公也离不开它,微信也注意到大家的意愿,所以也开发了电脑端的微信,不过有时候电脑版的微信也不好用,遇到紧急情况需要通知同事的时候又发现打不开了,通常遇上这种情况,我们要采取这些措施。解决办法如下:电脑版微信打不开是怎么一回事?第一步要做的就是,排查网络或是电脑系统的问题,可以重启试试。排除电脑或者网络问题以后,那可能是微信客户端不稳定。也许是文件损坏了或者是系统…

  • 主成分分析

    主成分分析

    2021年12月17日
  • upx 手动脱壳[通俗易懂]

    upx 手动脱壳[通俗易懂]查壳UPX0.89.6-1.02/1.05-2.90(Delphi)stub->Markus&Laszloupx这类压缩壳手动脱壳非常简单。一、查找oep

  • PHP5.6 和PHP7.0区别

    PHP5.6 和PHP7.0区别

发表回复

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

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