Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

雁过留声——模拟+字典树

Posted by fanhqme at 2010-01-03 17:39:01 on Problem 2314 and last updated at 2010-01-03 17:40:40

其实准确的说这题我使用的数据结构是“三叉搜索树”。
所谓“三叉搜索树”是我从《程序员》杂志上看到的一种
比较省内存的字典树，正好拿这题来试试。对此感兴趣的不妨参看
《程序员》2009年11月刊《用三叉搜索树实现高效率的“自动完成”》

关于这种解释器类的模拟题，我比较喜欢的一种思路，是
先创造一个比题目描述的语言更低级、容易实现的语言，
然后把输入到的程序翻译，或说是编译成这种语言。
我构想了一种很适合这题的类似汇编的语言，它是由若干条指令组成，
运行的时候依次执行（除非遇到跳转语句），同时维护两个寄存器的值。
指令集为：
0 nop//空指令
1 ld1 A//把内存地址为A的变量载入第一寄存器
2 write A//把第一寄存器的数据复制到内存地址A
3 ld2 a//把整数a载入第二寄存器
4 swap//交换第一、二寄存器的数据
5 add//把第二寄存器的值与第一寄存器的值相加，结果保存在第一寄存器中
6 sub//减
7 mul//乘
8 div//除，题目没要求，我自己添加的，方便以后多次利用这段代码。
9 comp>//如果第一寄存器的值大于第二寄存器，则第一寄存器的值设为1，否则为0
10 comp>=//大于等于
11 comp<//小于
12 comp<=//小于等于
13 comp=//等于
14 comp!=//不等于，这些多余的指令也是我自己加入的，方便以后利用。
15 goto a//跳转到第a条指令
16 ifgoto a//如果第一寄存器的值不是0，跳转到第a条指令
17 exit//退出程序，返回值为第一寄存器的数据
18 print A//打印内存地址为A的变量
19 read A//读入变量，都是我自己添的
20 rem//除法求余数
这种语言的执行器是十分容易写的，关键就是怎么把POJ语翻译过来。
翻译的过程需要一点想象力，举一些例子：
对于形如A=B-C,翻译为
ld1 B
swap
ld1 C
swap
sub
write A
对于形如A=B*2，翻译为
ld1 B
ld2 2
mul
write A
对于形如A=B，翻译为
ld1 B
write A
对于形如A=1，翻译为
ld2 1
swap
write A
对于形如if (A>B){...}，翻译为
ld1 A
swap
ld1 B
swap
comp>
ifgoto:lable1
goto lable2
lable1:
...
lable2:
nop
对于形如while (A>B){...}，翻译为
lable0:
nop
ld1 A
swap
ld1 B
swap
comp>
ifgoto:lable1
goto lable2
lable1:
...
goto lable0
lable2:
nop

为了方便，我先把所有的输入都读到一个数组中。
然后，写一个专门的函数用于分离出标示符（变量名、运算符、括号...）。
再根据赋值、条件、循环语句的特点，把每个句子的类型识别出来，分别进行翻译。
对于POJ语中出现的变量，建一个字典树，编号。
if语句条件为假的时候应当跳转到的语句编号无法立刻确定，
我的解决方案是：建立一个栈，存贮待定的语句编号的位置，每遇到一个回大括号，
就处理一下。
while语句同理。

提供一个十分有用的测试样例：
aaa=2;
aa=-10;
while (-100<=aa){
aa=aa-3;
aa=aa-aaa;
}
#aa;
最后应该输出-105，请注意你的程序对负号的处理。
附送一个统计冰雹猜想中迭代次数的程序
x=121;c=0;
while (1<x){
y=0;i=0;
while (y<x){
y=y+2;
i=i+1;
}
flg=0;
if (x==y){
flg=1;
}
if (flg==1){
x=i;
}
if (flg==0){
x=x*3;
x=x+1;
}
c=c+1;
}
#c;
应当输出95

这题竟然非常仁慈的没有卡常数。
我用空循环10000*10000次测试，我的解释器执行效率约为1/66。
while (x<10000){
y=0;
while (y<10000){
y=y+1;
i=i+1;
}
x=x+1;
}
同样的代码，解释执行跑了26秒，而用直接编译执行只跑了0.390秒。

代码示例：
struct Tnode{
	char c;
	int id;
	Tnode *lc,*rc,*son;
	Tnode(){id=-1;lc=rc=son=NULL;}
}Tpool[WMax],*Ttop;
struct Trie3{
	Tnode *root;
	int cnt;
	Trie3(){root=NULL;cnt=0;}
	int get(char *a,int &flag){flag=0;
		Tnode **p;
		for (p=&root;*a;a++){
			while (*p && *a!=(*p)->c){
				if (*a<(*p)->c)p=&((*p)->lc);
				else p=&((*p)->rc);
			}
			if (!*p){
				*p=Ttop++;(*p)->c=*a;
			}
			if (a[1])p=&((*p)->son);
			else if ((*p)->id==-1)(*p)->id=cnt++,flag=1;
		}
		return (*p)->id;
	}
}dictionary;
int alpha(char c){
	return '0'<=c && c<='9' || 'a'<=c && c<='z' || 'A'<=c && c<='Z' || c=='_';
}
int getstring(int &a,int flag=1){
	char c;
	while (c=file[pt],c==' ' || c==10 || c==13 || c=='\t')pt++;
	if (!file[pt])return -1;
	int x,y;
	if (flag && file[pt]=='-' && '0'<=file[pt+1] && file[pt+1]<='9'){y=-1;pt++;}
	else y=1;
	if ('0'<=file[pt] && file[pt]<='9'){
		for (x=0;'0'<=file[pt] && file[pt]<='9';pt++)
			x=10*x+file[pt]-'0';
		a=x*y;return 0;
	}
	if (file[pt]=='(')return pt++,1;
	if (file[pt]==')')return pt++,2;
	if (file[pt]=='{')return pt++,3;
	if (file[pt]=='}')return pt++,4;
	if (file[pt]==';')return pt++,5;
	if (file[pt]=='#')return pt++,6;
	if (file[pt]=='^')return pt++,21;
	if (file[pt]=='@')return pt++,22;
	if (file[pt]=='=' && file[pt+1]=='=')return pt+=2,20;
	if (file[pt]=='=')return pt++,7;
	if (file[pt]=='!' && file[pt+1]=='=')return pt+=2,19;
	if (file[pt]=='<' && file[pt+1]=='=')return pt+=2,8;
	if (file[pt]=='<')return pt++,9;
	if (file[pt]=='>' && file[pt+1]=='=')return pt+=2,10;
	if (file[pt]=='>')return pt++,11;
	if (file[pt]=='+')return pt++,12;
	if (file[pt]=='-')return pt++,13;
	if (file[pt]=='*')return pt++,14;
	if (file[pt]=='/')return pt++,15;
	if (file[pt]=='%')return pt++,23;
	char buf[1000];
	if (file[pt]=='i' && file[pt+1]=='f' && !alpha(file[pt+2]))
		return pt+=2,16;
	if (file[pt]=='w' && file[pt+1]=='h' && file[pt+2]=='i'
		&& file[pt+3]=='l' && file[pt+4]=='e' && !alpha(file[pt+5]))
		return pt+=5,17;
	buf[0]=0;
	for (int i=0;alpha(file[pt]);pt++,i++){
			buf[i]=file[pt];
			buf[i+1]=0;
		}
	a=dictionary.get(buf,x);
	return 18;
}
void read1(){
	int x,type;
	type=getstring(x);
	if (type==0){
		line[C++]=3;line[C++]=x;line[C++]=4;
	}else if (type==18){
		line[C++]=1;line[C++]=x;
	}else puts("can't find num1");
}
void read2(){
	int x,type;
	type=getstring(x);
	if (type==0){
		line[C++]=3;line[C++]=x;
	}else if (type==18){
		line[C++]=4;line[C++]=1;line[C++]=x;line[C++]=4;
	}else puts("can't find num2");
}
void compile(){
	char c;
	int type,x,sk;
	file[0]=0;
	for (int i=0;c=fgetc(stdin),c!=EOF && c!='`';i++){
		file[i]=c;
		file[i+1]=0;
	}
	pt=0;C=0;sk=0;
	int a,b;
	while (file[pt]){
		type=getstring(x);
		if (type==-1)break;
		if (type==6){
			getstring(x);
			line[C++]=1;line[C++]=x;line[C++]=17;
			if (getstring(x)!=5)puts("can't find ;");
		}else if (type==21){
			getstring(x);
			line[C++]=18;line[C++]=x;
			if (getstring(x)!=5)puts("can't find ;");
		}else if (type==22){
			getstring(x);
			line[C++]=19;line[C++]=x;
			if (getstring(x)!=5)puts("can't find ;");
		}else if (type==18){
			a=x;
			if (getstring(x)!=7)puts("can't find =");
			read1();
			type=getstring(x,0);
			if (type==5){
				line[C++]=2;line[C++]=a;
			}else{
				b=type;
				read2();
				type=getstring(x);
				if (type!=5)puts("can't find ;");
				if (b==12)line[C++]=5;
				else if (b==13)line[C++]=6;
				else if (b==14)line[C++]=7;
				else if (b==15)line[C++]=8;
				else if (b==23)line[C++]=20;
				else puts("can't find +-*/");
				line[C++]=2;line[C++]=a;
			}
		}else if (type==16){
			type=getstring(x);
			if (type!=1)puts("can't find (");
			read1();
			type=getstring(x);
			b=type;
			read2();
			type=getstring(x);
			if (type!=2)puts("can't find )");
			if (b==20)line[C++]=13;
			else if (b==19)line[C++]=14;
			else if (b==8)line[C++]=12;
			else if (b==9)line[C++]=11;
			else if (b==10)line[C++]=10;
			else if (b==11)line[C++]=9;
			else puts("can't find <>=!");
			line[C++]=16;line[C]=C+3;C++;
			line[C++]=15;
			line[C]=-1;stack[sk++]=C;C++;
			line[C++]=0;
			type=getstring(x);
			if (type!=3)puts("can't find {");
		}else if (type==17){
			line[C]=0;stack[sk++]=C;C++;
			type=getstring(x);
			if (type!=1)puts("can't find (");
			read1();
			type=getstring(x);
			b=type;
			read2();
			type=getstring(x);
			if (type!=2)puts("can't find )");
			if (b==20)line[C++]=13;
			else if (b==19)line[C++]=14;
			else if (b==8)line[C++]=12;
			else if (b==9)line[C++]=11;
			else if (b==10)line[C++]=10;
			else if (b==11)line[C++]=9;
			else puts("can't find <>=!");
			line[C++]=16;line[C]=C+3;C++;
			line[C++]=15;
			line[C]=-2;stack[sk++]=C;C++;
			line[C++]=0;
			type=getstring(x);
			if (type!=3)puts("can't find {");
		}else if (type==4){
			if (!sk)puts("where is }?");
			else if (line[stack[sk-1]]==-1){
				line[C++]=0;
				line[stack[sk-1]]=C-1;
				sk--;
			}else{
				line[C++]=15;line[C++]=stack[sk-2];
				line[C++]=0;
				line[stack[sk-1]]=C-1;
				sk-=2;
			}
		}
	}
	line[C++]=17;
	//puts("compile success!");
	/*for (int i=0;i<C;i++)
		printf("%5d:%d\n",i,line[i]);*/
}
int run(){
	int id;
	int X1,X2,t;
	X1=X2=0;
	for (int i=0;i<dictionary.cnt;i++)
		memo[i]=0;
	id=0;
	while (1){
		//printf("id=%-5d X1=%-8d X2=%-8d\n",id,X1,X2);
		if (line[id]==0){
			id++;
		}else if (line[id]==1){
			X1=memo[line[id+1]];
			id+=2;
		}else if (line[id]==2){
			memo[line[id+1]]=X1;
			id+=2;
		}else if (line[id]==3){
			X2=line[id+1];
			id+=2;
		}else if (line[id]==4){
			t=X1;X1=X2;X2=t;
			id++;
		}else if (line[id]==5){
			X1+=X2;
			id++;
		}else if (line[id]==6){
			X1-=X2;
			id++;
		}else if (line[id]==7){
			X1*=X2;
			id++;
		}else if (line[id]==8){
			if (X2)X1/=X2;
			id++;
		}else if (line[id]==9){
			X1=(X1>X2);
			id++;
		}else if (line[id]==10){
			X1=(X1>=X2);
			id++;
		}else if (line[id]==11){
			X1=(X1<X2);
			id++;
		}else if (line[id]==12){
			X1=(X1<=X2);
			id++;
		}else if (line[id]==13){
			X1=(X1==X2);
			id++;
		}else if (line[id]==14){
			X1=(X1!=X2);
			id++;
		}else if (line[id]==15){
			id=line[id+1];
		}else if (line[id]==16){
			if (X1)id=line[id+1];
			else id+=2;
		}else if (line[id]==17){
			break;
		}else if (line[id]==18){
			printf("%d\n",memo[line[id+1]]);
			id+=2;
		}else if (line[id]==19){
			scanf("%d",&memo[line[id+1]]);
			id+=2;
		}else if (line[id]==20){
			if (X2)X1%=X2;
			id++;
		}else{
			puts("what's this?");
			id++;
		}
	}
	return X1;
}

        compile();
	int ret;
	ret=run();
	printf("%d\n",ret);

Followed by:

Post your reply here:

User ID:
Password:
Title:

Content:

> 其实准确的说这题我使用的数据结构是“三叉搜索树”。
> 所谓“三叉搜索树”是我从《程序员》杂志上看到的一种
> 比较省内存的字典树，正好拿这题来试试。对此感兴趣的不妨参看
> 《程序员》2009年11月刊《用三叉搜索树实现高效率的“自动完成”》
> 
> 关于这种解释器类的模拟题，我比较喜欢的一种思路，是
> 先创造一个比题目描述的语言更低级、容易实现的语言，
> 然后把输入到的程序翻译，或说是编译成这种语言。
> 我构想了一种很适合这题的类似汇编的语言，它是由若干条指令组成，
> 运行的时候依次执行（除非遇到跳转语句），同时维护两个寄存器的值。
> 指令集为：
> 0 nop//空指令
> 1 ld1 A//把内存地址为A的变量载入第一寄存器
> 2 write A//把第一寄存器的数据复制到内存地址A
> 3 ld2 a//把整数a载入第二寄存器
> 4 swap//交换第一、二寄存器的数据
> 5 add//把第二寄存器的值与第一寄存器的值相加，结果保存在第一寄存器中
> 6 sub//减
> 7 mul//乘
> 8 div//除，题目没要求，我自己添加的，方便以后多次利用这段代码。
> 9 comp>//如果第一寄存器的值大于第二寄存器，则第一寄存器的值设为1，否则为0
> 10 comp>=//大于等于
> 11 comp<//小于
> 12 comp<=//小于等于
> 13 comp=//等于
> 14 comp!=//不等于，这些多余的指令也是我自己加入的，方便以后利用。
> 15 goto a//跳转到第a条指令
> 16 ifgoto a//如果第一寄存器的值不是0，跳转到第a条指令
> 17 exit//退出程序，返回值为第一寄存器的数据
> 18 print A//打印内存地址为A的变量
> 19 read A//读入变量，都是我自己添的
> 20 rem//除法求余数
> 这种语言的执行器是十分容易写的，关键就是怎么把POJ语翻译过来。
> 翻译的过程需要一点想象力，举一些例子：
> 对于形如A=B-C,翻译为
> ld1 B
> swap
> ld1 C
> swap
> sub
> write A
> 对于形如A=B*2，翻译为
> ld1 B
> ld2 2
> mul
> write A
> 对于形如A=B，翻译为
> ld1 B
> write A
> 对于形如A=1，翻译为
> ld2 1
> swap
> write A
> 对于形如if (A>B){...}，翻译为
> ld1 A
> swap
> ld1 B
> swap
> comp>
> ifgoto:lable1
> goto lable2
> lable1:
> ...
> lable2:
> nop
> 对于形如while (A>B){...}，翻译为
> lable0:
> nop
> ld1 A
> swap
> ld1 B
> swap
> comp>
> ifgoto:lable1
> goto lable2
> lable1:
> ...
> goto lable0
> lable2:
> nop
> 
> 为了方便，我先把所有的输入都读到一个数组中。
> 然后，写一个专门的函数用于分离出标示符（变量名、运算符、括号...）。
> 再根据赋值、条件、循环语句的特点，把每个句子的类型识别出来，分别进行翻译。
> 对于POJ语中出现的变量，建一个字典树，编号。
> if语句条件为假的时候应当跳转到的语句编号无法立刻确定，
> 我的解决方案是：建立一个栈，存贮待定的语句编号的位置，每遇到一个回大括号，
> 就处理一下。
> while语句同理。
> 
> 提供一个十分有用的测试样例：
> aaa=2;
> aa=-10;
> while (-100<=aa){
> aa=aa-3;
> aa=aa-aaa;
> }
> #aa;
> 最后应该输出-105，请注意你的程序对负号的处理。
> 附送一个统计冰雹猜想中迭代次数的程序
> x=121;c=0;
> while (1<x){
> y=0;i=0;
> while (y<x){
> y=y+2;
> i=i+1;
> }
> flg=0;
> if (x==y){
> flg=1;
> }
> if (flg==1){
> x=i;
> }
> if (flg==0){
> x=x*3;
> x=x+1;
> }
> c=c+1;
> }
> #c;
> 应当输出95
> 
> 这题竟然非常仁慈的没有卡常数。
> 我用空循环10000*10000次测试，我的解释器执行效率约为1/66。
> while (x<10000){
> y=0;
> while (y<10000){
> y=y+1;
> i=i+1;
> }
> x=x+1;
> }
> 同样的代码，解释执行跑了26秒，而用直接编译执行只跑了0.390秒。
> 
> 代码示例：
> struct Tnode{
> 	char c;
> 	int id;
> 	Tnode *lc,*rc,*son;
> 	Tnode(){id=-1;lc=rc=son=NULL;}
> }Tpool[WMax],*Ttop;
> struct Trie3{
> 	Tnode *root;
> 	int cnt;
> 	Trie3(){root=NULL;cnt=0;}
> 	int get(char *a,int &flag){flag=0;
> 		Tnode **p;
> 		for (p=&root;*a;a++){
> 			while (*p && *a!=(*p)->c){
> 				if (*a<(*p)->c)p=&((*p)->lc);
> 				else p=&((*p)->rc);
> 			}
> 			if (!*p){
> 				*p=Ttop++;(*p)->c=*a;
> 			}
> 			if (a[1])p=&((*p)->son);
> 			else if ((*p)->id==-1)(*p)->id=cnt++,flag=1;
> 		}
> 		return (*p)->id;
> 	}
> }dictionary;
> int alpha(char c){
> 	return '0'<=c && c<='9' || 'a'<=c && c<='z' || 'A'<=c && c<='Z' || c=='_';
> }
> int getstring(int &a,int flag=1){
> 	char c;
> 	while (c=file[pt],c==' ' || c==10 || c==13 || c=='\t')pt++;
> 	if (!file[pt])return -1;
> 	int x,y;
> 	if (flag && file[pt]=='-' && '0'<=file[pt+1] && file[pt+1]<='9'){y=-1;pt++;}
> 	else y=1;
> 	if ('0'<=file[pt] && file[pt]<='9'){
> 		for (x=0;'0'<=file[pt] && file[pt]<='9';pt++)
> 			x=10*x+file[pt]-'0';
> 		a=x*y;return 0;
> 	}
> 	if (file[pt]=='(')return pt++,1;
> 	if (file[pt]==')')return pt++,2;
> 	if (file[pt]=='{')return pt++,3;
> 	if (file[pt]=='}')return pt++,4;
> 	if (file[pt]==';')return pt++,5;
> 	if (file[pt]=='#')return pt++,6;
> 	if (file[pt]=='^')return pt++,21;
> 	if (file[pt]=='@')return pt++,22;
> 	if (file[pt]=='=' && file[pt+1]=='=')return pt+=2,20;
> 	if (file[pt]=='=')return pt++,7;
> 	if (file[pt]=='!' && file[pt+1]=='=')return pt+=2,19;
> 	if (file[pt]=='<' && file[pt+1]=='=')return pt+=2,8;
> 	if (file[pt]=='<')return pt++,9;
> 	if (file[pt]=='>' && file[pt+1]=='=')return pt+=2,10;
> 	if (file[pt]=='>')return pt++,11;
> 	if (file[pt]=='+')return pt++,12;
> 	if (file[pt]=='-')return pt++,13;
> 	if (file[pt]=='*')return pt++,14;
> 	if (file[pt]=='/')return pt++,15;
> 	if (file[pt]=='%')return pt++,23;
> 	char buf[1000];
> 	if (file[pt]=='i' && file[pt+1]=='f' && !alpha(file[pt+2]))
> 		return pt+=2,16;
> 	if (file[pt]=='w' && file[pt+1]=='h' && file[pt+2]=='i'
> 		&& file[pt+3]=='l' && file[pt+4]=='e' && !alpha(file[pt+5]))
> 		return pt+=5,17;
> 	buf[0]=0;
> 	for (int i=0;alpha(file[pt]);pt++,i++){
> 			buf[i]=file[pt];
> 			buf[i+1]=0;
> 		}
> 	a=dictionary.get(buf,x);
> 	return 18;
> }
> void read1(){
> 	int x,type;
> 	type=getstring(x);
> 	if (type==0){
> 		line[C++]=3;line[C++]=x;line[C++]=4;
> 	}else if (type==18){
> 		line[C++]=1;line[C++]=x;
> 	}else puts("can't find num1");
> }
> void read2(){
> 	int x,type;
> 	type=getstring(x);
> 	if (type==0){
> 		line[C++]=3;line[C++]=x;
> 	}else if (type==18){
> 		line[C++]=4;line[C++]=1;line[C++]=x;line[C++]=4;
> 	}else puts("can't find num2");
> }
> void compile(){
> 	char c;
> 	int type,x,sk;
> 	file[0]=0;
> 	for (int i=0;c=fgetc(stdin),c!=EOF && c!='`';i++){
> 		file[i]=c;
> 		file[i+1]=0;
> 	}
> 	pt=0;C=0;sk=0;
> 	int a,b;
> 	while (file[pt]){
> 		type=getstring(x);
> 		if (type==-1)break;
> 		if (type==6){
> 			getstring(x);
> 			line[C++]=1;line[C++]=x;line[C++]=17;
> 			if (getstring(x)!=5)puts("can't find ;");
> 		}else if (type==21){
> 			getstring(x);
> 			line[C++]=18;line[C++]=x;
> 			if (getstring(x)!=5)puts("can't find ;");
> 		}else if (type==22){
> 			getstring(x);
> 			line[C++]=19;line[C++]=x;
> 			if (getstring(x)!=5)puts("can't find ;");
> 		}else if (type==18){
> 			a=x;
> 			if (getstring(x)!=7)puts("can't find =");
> 			read1();
> 			type=getstring(x,0);
> 			if (type==5){
> 				line[C++]=2;line[C++]=a;
> 			}else{
> 				b=type;
> 				read2();
> 				type=getstring(x);
> 				if (type!=5)puts("can't find ;");
> 				if (b==12)line[C++]=5;
> 				else if (b==13)line[C++]=6;
> 				else if (b==14)line[C++]=7;
> 				else if (b==15)line[C++]=8;
> 				else if (b==23)line[C++]=20;
> 				else puts("can't find +-*/");
> 				line[C++]=2;line[C++]=a;
> 			}
> 		}else if (type==16){
> 			type=getstring(x);
> 			if (type!=1)puts("can't find (");
> 			read1();
> 			type=getstring(x);
> 			b=type;
> 			read2();
> 			type=getstring(x);
> 			if (type!=2)puts("can't find )");
> 			if (b==20)line[C++]=13;
> 			else if (b==19)line[C++]=14;
> 			else if (b==8)line[C++]=12;
> 			else if (b==9)line[C++]=11;
> 			else if (b==10)line[C++]=10;
> 			else if (b==11)line[C++]=9;
> 			else puts("can't find <>=!");
> 			line[C++]=16;line[C]=C+3;C++;
> 			line[C++]=15;
> 			line[C]=-1;stack[sk++]=C;C++;
> 			line[C++]=0;
> 			type=getstring(x);
> 			if (type!=3)puts("can't find {");
> 		}else if (type==17){
> 			line[C]=0;stack[sk++]=C;C++;
> 			type=getstring(x);
> 			if (type!=1)puts("can't find (");
> 			read1();
> 			type=getstring(x);
> 			b=type;
> 			read2();
> 			type=getstring(x);
> 			if (type!=2)puts("can't find )");
> 			if (b==20)line[C++]=13;
> 			else if (b==19)line[C++]=14;
> 			else if (b==8)line[C++]=12;
> 			else if (b==9)line[C++]=11;
> 			else if (b==10)line[C++]=10;
> 			else if (b==11)line[C++]=9;
> 			else puts("can't find <>=!");
> 			line[C++]=16;line[C]=C+3;C++;
> 			line[C++]=15;
> 			line[C]=-2;stack[sk++]=C;C++;
> 			line[C++]=0;
> 			type=getstring(x);
> 			if (type!=3)puts("can't find {");
> 		}else if (type==4){
> 			if (!sk)puts("where is }?");
> 			else if (line[stack[sk-1]]==-1){
> 				line[C++]=0;
> 				line[stack[sk-1]]=C-1;
> 				sk--;
> 			}else{
> 				line[C++]=15;line[C++]=stack[sk-2];
> 				line[C++]=0;
> 				line[stack[sk-1]]=C-1;
> 				sk-=2;
> 			}
> 		}
> 	}
> 	line[C++]=17;
> 	//puts("compile success!");
> 	/*for (int i=0;i<C;i++)
> 		printf("%5d:%d\n",i,line[i]);*/
> }
> int run(){
> 	int id;
> 	int X1,X2,t;
> 	X1=X2=0;
> 	for (int i=0;i<dictionary.cnt;i++)
> 		memo[i]=0;
> 	id=0;
> 	while (1){
> 		//printf("id=%-5d X1=%-8d X2=%-8d\n",id,X1,X2);
> 		if (line[id]==0){
> 			id++;
> 		}else if (line[id]==1){
> 			X1=memo[line[id+1]];
> 			id+=2;
> 		}else if (line[id]==2){
> 			memo[line[id+1]]=X1;
> 			id+=2;
> 		}else if (line[id]==3){
> 			X2=line[id+1];
> 			id+=2;
> 		}else if (line[id]==4){
> 			t=X1;X1=X2;X2=t;
> 			id++;
> 		}else if (line[id]==5){
> 			X1+=X2;
> 			id++;
> 		}else if (line[id]==6){
> 			X1-=X2;
> 			id++;
> 		}else if (line[id]==7){
> 			X1*=X2;
> 			id++;
> 		}else if (line[id]==8){
> 			if (X2)X1/=X2;
> 			id++;
> 		}else if (line[id]==9){
> 			X1=(X1>X2);
> 			id++;
> 		}else if (line[id]==10){
> 			X1=(X1>=X2);
> 			id++;
> 		}else if (line[id]==11){
> 			X1=(X1<X2);
> 			id++;
> 		}else if (line[id]==12){
> 			X1=(X1<=X2);
> 			id++;
> 		}else if (line[id]==13){
> 			X1=(X1==X2);
> 			id++;
> 		}else if (line[id]==14){
> 			X1=(X1!=X2);
> 			id++;
> 		}else if (line[id]==15){
> 			id=line[id+1];
> 		}else if (line[id]==16){
> 			if (X1)id=line[id+1];
> 			else id+=2;
> 		}else if (line[id]==17){
> 			break;
> 		}else if (line[id]==18){
> 			printf("%d\n",memo[line[id+1]]);
> 			id+=2;
> 		}else if (line[id]==19){
> 			scanf("%d",&memo[line[id+1]]);
> 			id+=2;
> 		}else if (line[id]==20){
> 			if (X2)X1%=X2;
> 			id++;
> 		}else{
> 			puts("what's this?");
> 			id++;
> 		}
> 	}
> 	return X1;
> }
> 
>         compile();
> 	int ret;
> 	ret=run();
> 	printf("%d\n",ret);

Home Page Go Back To top