Infinite Dictionaries

Infinite Dictionaries

时间: 1ms        内存:128M

描述:

A dictionary is a set of key-value pairs, for example:

 

{'color':'red', 'price':2, 7:'test', 100:-100}

 

As you can see, keys and values can be strings or integers. What’s more, values can also be dictionaries or variable references. Here is the formal definition of terms that will be used soon:

 

key   ::=      INTEGER | STRING

value ::=      INTEGER | STRING | dict

pair  ::=      key ':' value

dict  ::=      '{' [pair (',' pair)*] '}'

var   ::=      'a'|'b'|'c'|...|'z'

slot  ::=      var('[' key ']')*

lvar  ::=      slot

rvar  ::=      slot | value

 

Here ('[' key ']')* means zero or more subscripts, [pair (',' pair)*] means zero or more key-value pairs.

 

Strings are always enclosed by single quotes ('') and consists of up to 10 lower-case letters. Integers always have absolute values of no more than 1000. You can insert spaces anywhere, except inside strings or integers. For example, { 'a':-1} and {'a' : -1   } are the same, but {'a b':1} and {'a':- 1} are both illegal.

 

Your task is to execute a series of commands and print the results. There are 3 kinds of commands:

 

1. Assignment: <lvar> = <rval>

 

After assigning a slot to a slot (rather than a value), the left-hand slot will be holding a reference to the right-hand. For example, After executing the following commands, b[1][0] is 1, rather than 0:

 

a = {0:0}

b = {}

b[1] = a

a[0] = 1

 

Slots must be assigned before it is read or subscripted, and integers and strings cannot be subscripted. Consider the following comammd list:

 

c = {}

c[0] = 3

c[1] = c[0]

d[0] = 'i'

c = d

d = c[1]['a']

c[2][2] = 2

 

The first three commands are legal, but the next two are both illegal because slot d must be assigned before it is read or subscripted. The last three are also illegal.

 

2. Length: length(<slot>)

 

Output the number of key-value pairs in the slot. Note that nested pairs are not counted. For example:

 

a = {0: {0:0, 1:1}}

length(a)

 

will output 1, not 3. In this command, it is guaranteed that <slot> is storing a dictionary, not a string or an integer.

 

3. Infinity test: test(<slot>)

 

If the slot can be subscripted indefinitely, output 1. Otherwise, output 0. For example, after executing the following command list:

 

d = {}

d[0] = d

 

Then d is infinite, since d[0][0][0][0][0][0]... is always d. In this command, it is guaranteed that <slot> is storing a dictionary, not a string or an integer.

 

Input

The input contains at most 10000 lines of commands, each line will be non-empty and will contain no more than 300 characters. All the commands are legal.

 

Output

Print the output (one line for each length/test command).

输入:

输出:

示例输入:

c = {}
d = {'color': 'red', 'price': 2, 7: 'test', 100: -100}
length(d)
d[7] = {'this': 'is', 'a': 'book'}
length(d)
d[8] = {'this' : 'is', 'another' : {'a' : 'book', 'b': 'book2'} }
length(d)
c[7] = c
test(c)
test(d)
length(c)
d[0] = c
length(d)
test(d[0])

示例输出:

4
4
5
1
0
1
6
1

提示:

参考答案(内存最优[5824]):

#include<vector> 
#include<map> 
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;

struct rec
{
	int flag;
	int x;
	string y;
	int z;
    rec() { flag=0; x=0; y=""; z=0; }    
};

bool operator<(rec a,rec b)
{
	if (a.flag!=b.flag)
		return a.flag<b.flag;
	if (a.x!=b.x)
		return a.x<b.x;
	if (a.y!=b.y)
		return a.y<b.y;
	return a.z<b.z;
}

rec v[100];
map<rec,rec> a[100000];
string s;
int n;
int zhan[100000];
int used[100000];
int used1[100000];

rec parsemap(int x,int y);

int dfs(int x)
{
	for (map<rec,rec>::iterator it=a[x].begin();it!=a[x].end();it++)
	{
		if (it->second.flag==2)
		{
			if (used[it->second.z]==0)
			{
				used[it->second.z]=1;
				used1[it->second.z]=1;
				if (dfs(it->second.z)) return 1;
				used1[it->second.z]=0;
			}
			else if (used1[it->second.z]==1) return 1;
		}
	}
	return 0;
}

int test(int x)
{
	int top,bottom;
	top=0;bottom=1;
	memset(used,0,sizeof(used));
	memset(used1,0,sizeof(used1));
	used[x]=1;
	used1[x]=1;
	return dfs(x);
}

rec parsekey(int x,int y)
{
	rec p;
	while (s[x]==' ') x++;
	while (s[y]==' ') y--;
	if (s[x]=='\'')
	{
		p.flag=1;
		p.x=0;
		p.y=s.substr(x+1,y-x-1);
		p.z=0;
	}
	else
	{
		p.flag=0;
		p.x=atoi(s.substr(x,y-x+1).c_str());
		p.y="";
		p.z=0;
	}
	return p;
}

pair<rec,rec> parsepair(int x,int y)
{
	pair<rec,rec> ans;
	int i;
	for (i=x;i<=y;i++)
		if (s[i]==':') break;
	ans.first=parsekey(x,i-1);
	
	i++;
	for (;i<=y;i++)
		if (s[i]!=' ') break;


	if (s[i]=='{')
	{
		ans.second=parsemap(i,y);
	}
	else
	{
		ans.second=parsekey(i,y);
	}
	return ans;
}

rec parsemap(int x,int y)
{
	int i,j,prev,cnt;
	pair<rec,rec> tmp;
	rec ans;
	ans.flag=2;
	ans.x=0;
	ans.y="";
	ans.z=n;
	n++;
	cnt=0;
	for (i=x;i<=y;i++)
		if (s[i]!=' ') cnt++;
	if (cnt==2)
	{
		return ans;
	}
	j=0;
	i=x+1;
	prev=x;
	while (1)
	{
		for (;i<y;i++)
		{
			if (s[i]=='{') j++;
			if (s[i]=='}') j--;
			if ((j==0)&&(s[i]==',')) break;
		}
		tmp=parsepair(prev+1,i-1);
		a[ans.z][tmp.first]=tmp.second;
		if (i==y)
		{
			break;
		}
		prev=i;
		i++;
	}
	return ans;
}

pair<int,rec> parseleft(int x,int y)
{
	pair<int,rec> p;
	rec q;
	int i,l,r;
	for (i=x;i<=y;i++) if (s[i]!=' ') break;

	p.first=s[i]-'a';
	p.second.flag=-1;
	p.second.x=0;
	p.second.y="";
	p.second.z=0;
	while (1)
	{
		i++;
		for (;i<=y&&i<s.length();i++)
			if (s[i]=='[') break;
		l=i;
		for (;i<=y&&i<s.length();i++)
			if (s[i]==']') break;
		r=i;
		if (i>y) break;
		q=parsekey(l+1,r-1);
		if (p.second.flag==-1)
		{
			p.first=v[p.first].z;
			p.second=q;
		}
		else
		{
			p.first=a[p.first][p.second].z;
			p.second=q;
		}
	}
	return p;
}

rec parseright(int x,int y)
{
	rec ans;
	while (s[x]==' ') x++;
	while (s[y]==' ') y--;
	if ((s[x]>='a')&&(s[x]<='z'))
	{
		pair<int,rec> tmp=parseleft(x,y);
		if (tmp.second.flag==-1)
		{
			ans.flag=2;
			ans.x=0;
			ans.y="";
			ans.z=v[tmp.first].z;
		}
		else
		{
			ans=a[tmp.first][tmp.second];
		}
		return ans;
	}
	if (s[x]=='{')
	{
		ans=parsemap(x,y);
		return ans;
	}
	ans=parsekey(x,y);
	return ans;
}

int main()
{
	int i,p;
	char ss[300];
	n=0;
	for (i=0;i<26;i++)
		v[i].z=-1;
	while (1)
	{
		ss[0]=0;
		gets(ss);
		if (ss[0]==0) break;
		s=ss;
		p=s.find_first_of('=');
		if (p==-1)
		{
			p=s.find_first_of('(');
			pair<int,rec> tmp=parseleft(p+1,s.length()-2);
			int ind;
			if (tmp.second.flag==-1)
				ind=v[tmp.first].z;
			else
				ind=a[tmp.first][tmp.second].z;
			if (s[0]=='l')
			{
				printf("%d\n",a[ind].size());
			}
			else
			{
				printf("%d\n",test(ind));
			}
		}
		else
		{
			p=s.find_first_of('=');
			pair<int,rec> tmp=parseleft(0,p-1);
			if (tmp.second.flag==-1)
				v[tmp.first]=parseright(p+1,s.length()-1);
			else
				a[tmp.first][tmp.second]=parseright(p+1,s.length()-1);
		}
	}
	return 0;
}

参考答案(时间最优[268]):

#include<vector> 
#include<map> 
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;

struct rec
{
	int flag;
	int x;
	string y;
	int z;
    rec() { flag=0; x=0; y=""; z=0; }    
};

bool operator<(rec a,rec b)
{
	if (a.flag!=b.flag)
		return a.flag<b.flag;
	if (a.x!=b.x)
		return a.x<b.x;
	if (a.y!=b.y)
		return a.y<b.y;
	return a.z<b.z;
}

rec v[100];
map<rec,rec> a[100000];
string s;
int n;
int zhan[100000];
int used[100000];
int used1[100000];

rec parsemap(int x,int y);

int dfs(int x)
{
	for (map<rec,rec>::iterator it=a[x].begin();it!=a[x].end();it++)
	{
		if (it->second.flag==2)
		{
			if (used[it->second.z]==0)
			{
				used[it->second.z]=1;
				used1[it->second.z]=1;
				if (dfs(it->second.z)) return 1;
				used1[it->second.z]=0;
			}
			else if (used1[it->second.z]==1) return 1;
		}
	}
	return 0;
}

int test(int x)
{
	int top,bottom;
	top=0;bottom=1;
	memset(used,0,sizeof(used));
	memset(used1,0,sizeof(used1));
	used[x]=1;
	used1[x]=1;
	return dfs(x);
}

rec parsekey(int x,int y)
{
	rec p;
	while (s[x]==' ') x++;
	while (s[y]==' ') y--;
	if (s[x]=='\'')
	{
		p.flag=1;
		p.x=0;
		p.y=s.substr(x+1,y-x-1);
		p.z=0;
	}
	else
	{
		p.flag=0;
		p.x=atoi(s.substr(x,y-x+1).c_str());
		p.y="";
		p.z=0;
	}
	return p;
}

pair<rec,rec> parsepair(int x,int y)
{
	pair<rec,rec> ans;
	int i;
	for (i=x;i<=y;i++)
		if (s[i]==':') break;
	ans.first=parsekey(x,i-1);
	
	i++;
	for (;i<=y;i++)
		if (s[i]!=' ') break;


	if (s[i]=='{')
	{
		ans.second=parsemap(i,y);
	}
	else
	{
		ans.second=parsekey(i,y);
	}
	return ans;
}

rec parsemap(int x,int y)
{
	int i,j,prev,cnt;
	pair<rec,rec> tmp;
	rec ans;
	ans.flag=2;
	ans.x=0;
	ans.y="";
	ans.z=n;
	n++;
	cnt=0;
	for (i=x;i<=y;i++)
		if (s[i]!=' ') cnt++;
	if (cnt==2)
	{
		return ans;
	}
	j=0;
	i=x+1;
	prev=x;
	while (1)
	{
		for (;i<y;i++)
		{
			if (s[i]=='{') j++;
			if (s[i]=='}') j--;
			if ((j==0)&&(s[i]==',')) break;
		}
		tmp=parsepair(prev+1,i-1);
		a[ans.z][tmp.first]=tmp.second;
		if (i==y)
		{
			break;
		}
		prev=i;
		i++;
	}
	return ans;
}

pair<int,rec> parseleft(int x,int y)
{
	pair<int,rec> p;
	rec q;
	int i,l,r;
	for (i=x;i<=y;i++) if (s[i]!=' ') break;

	p.first=s[i]-'a';
	p.second.flag=-1;
	p.second.x=0;
	p.second.y="";
	p.second.z=0;
	while (1)
	{
		i++;
		for (;i<=y&&i<s.length();i++)
			if (s[i]=='[') break;
		l=i;
		for (;i<=y&&i<s.length();i++)
			if (s[i]==']') break;
		r=i;
		if (i>y) break;
		q=parsekey(l+1,r-1);
		if (p.second.flag==-1)
		{
			p.first=v[p.first].z;
			p.second=q;
		}
		else
		{
			p.first=a[p.first][p.second].z;
			p.second=q;
		}
	}
	return p;
}

rec parseright(int x,int y)
{
	rec ans;
	while (s[x]==' ') x++;
	while (s[y]==' ') y--;
	if ((s[x]>='a')&&(s[x]<='z'))
	{
		pair<int,rec> tmp=parseleft(x,y);
		if (tmp.second.flag==-1)
		{
			ans.flag=2;
			ans.x=0;
			ans.y="";
			ans.z=v[tmp.first].z;
		}
		else
		{
			ans=a[tmp.first][tmp.second];
		}
		return ans;
	}
	if (s[x]=='{')
	{
		ans=parsemap(x,y);
		return ans;
	}
	ans=parsekey(x,y);
	return ans;
}

int main()
{
	int i,p;
	char ss[300];
	n=0;
	for (i=0;i<26;i++)
		v[i].z=-1;
	while (1)
	{
		ss[0]=0;
		gets(ss);
		if (ss[0]==0) break;
		s=ss;
		p=s.find_first_of('=');
		if (p==-1)
		{
			p=s.find_first_of('(');
			pair<int,rec> tmp=parseleft(p+1,s.length()-2);
			int ind;
			if (tmp.second.flag==-1)
				ind=v[tmp.first].z;
			else
				ind=a[tmp.first][tmp.second].z;
			if (s[0]=='l')
			{
				printf("%d\n",a[ind].size());
			}
			else
			{
				printf("%d\n",test(ind));
			}
		}
		else
		{
			p=s.find_first_of('=');
			pair<int,rec> tmp=parseleft(0,p-1);
			if (tmp.second.flag==-1)
				v[tmp.first]=parseright(p+1,s.length()-1);
			else
				a[tmp.first][tmp.second]=parseright(p+1,s.length()-1);
		}
	}
	return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注