题解 P2229 【[HNOI2002]沙漠寻宝】
写在前面
实际上已近写过一篇这个题的题解了，这次只是稍作修改，压缩了以前又臭又长的代码，顺便再说明一下解题思路。
遇到的问题
一看这个题就知道是模拟，但是怎么模拟呢？
首先，读入与存储问题，如何准确的读入以及如何将输入的代码存起来。
其次，也是最难的，模拟程序运行，其中最关键的就是如何模拟循环的运行。
再者，计算器的问题，赋值语句与循环次数的计算。
解决方案
1.读入与存储，开一个二维的char数组（string也行，个人喜好），使用scanf("%s",s)读入，遇到空格跳过。
2.运行过程，其他语句不多说，就讲讲最关键的循环语句吧，看到有很多大佬都是用栈来模拟，个人不太习惯用栈模拟，于是用了类似于递归的方法，一层层进入，再退出。
3.有关计算器，由于题中给出了语句的执行次数的总和小于2000000次，那么计算器完全可以使用递归代替栈来写，并且完全不用担心会超时。
最后附上AC代码，代码中有解释
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#define MAXN 1001
using namespace std;
//函数总览，后面有解释
void read();
void work();
void find();
void write(char x[]);
int check(char x[]);
void run(char x[]);
void pre(char x[],int l,int r);
int calc(char x[],int l,int r);
void run_loo(char x[]);
int run_fu(char x[],int in,int enk);
char str[MAXN][MAXN],s[MAXN];
int tot=0,h=1,f[MAXN],ff[MAXN],sh[30];
const int sta=1,en=2,loo=3,con=4,wri=5,bre=6,fu=7;
//读入，处理掉空格
void read(){
while((scanf("%s",s))!=EOF){
if(s[0]!=' '){
strcpy(str[++tot],s);
}
}
}
//输出
void run_wri(char x[]){
++h;
printf("%d\n",run_fu(str[h],0,strlen(str[h])-1));
}
//预处理，找到循环的开始与结束
void find(){
int v[MAXN],v1=0;
for(int i=2;i<tot;i++){
if(check(str[i])==loo){
v1++;
v[v1]=i;
}else if(check(str[i])==en){
f[v[v1]]=i;
v1--;
}
}
}
//循环语句的递归实现
void run_loo(char x[]){
++h;
int t=run_fu(str[h],0,strlen(str[h])-1),tmp=h-1;
for(int i=1;i<=t;i++){
++h;
while(check(str[h])!=en){
if(check(str[h])==loo){
run_loo(x);
}else if(check(str[h])==con){
break;
}else if(check(str[h])==bre){
h=f[tmp];
return;
}
run(str[h]);
++h;
}
h=tmp+1;
}
h=f[tmp];
}
//每次使用计算器之前的预处理，为了处理表达式中有括号匹配的情况
void pre(char x[],int l,int r){
int v[MAXN],tot=0;
for(int i=l;i<=r;++i){
if(x[i]=='('){
v[++tot]=i;
}else if(x[i]==')'){
ff[v[tot]]=i;
--tot;
}
}
}
//递归实现简单计算器
int calc(char x[],int l,int r){
if(l==r&&x[l]>='a'&&x[l]<='z') return sh[x[l]-'a'];
if(x[l]=='('&&x[r]==')'&&ff[l]==r){
return calc(x,l+1,r-1);
}
int jia=0,cheng=0,isjia=0,ischeng=0,fa=0,isfa=0;
for(int i=l;i<=r;++i){
if(x[i]=='+') jia=i,isjia=1;
else if(x[i]=='*') cheng=i,ischeng=1;
else if(x[i]=='/') cheng=i,ischeng=0;
else if(x[i]=='-') jia=i,isjia=0;
else if(x[i]=='^') isfa=1,fa=i;
else if(x[i]=='(') i=ff[i]-1;
}
if(jia!=0){
if(isjia==1) return (calc(x,l,jia-1)+calc(x,jia+1,r));
else return (calc(x,l,jia-1)-calc(x,jia+1,r));
}else if(cheng!=0){
if(ischeng==1) return (calc(x,l,cheng-1)*calc(x,cheng+1,r));
else return (calc(x,l,cheng-1)/calc(x,cheng+1,r));
}else if(isfa!=0){
return (int)pow(calc(x,l,fa-1)*1.0,calc(x,fa+1,r)*1.0);
}else if(jia==0&&cheng==0&&isfa==0){
int tmp=0;
for(int i=l;i<=r;++i){
tmp=(tmp*10+(x[i]-'0'));
}
return tmp;
}
}
//赋值语句的运行，调用calc()函数计算
int run_fu(char x[],int in,int enk){
memset(ff,0,sizeof(ff));
pre(x,in,enk);
int res=calc(x,in,enk);
return res;
}
//判断是哪一种语句
int check(char x[]){
if(x[1]=='='){
return fu;
}else if(x[0]=='s'){
return sta;
}else if(x[0]=='e'&&x[1]=='n'){
return en;
}else if(x[0]=='l'&&x[1]=='o'){
return loo;
}else if(x[0]=='c'&&x[1]=='o'){
return con;
}else if(x[0]=='w'&&x[1]=='r'){
return wri;
}else if(x[0]=='b'&&x[1]=='r'){
return bre;
}else{
return -1;
}
}
//运行每一句语句
void run(char x[]){
int k=check(x);
switch(k){
case 3:run_loo(x); break;
case 5:run_wri(x); break;
case 7:sh[x[0]-'a']=run_fu(x,2,strlen(x)-1); break;
default:break;
}
}
//循环每一句语句
void work(){
while(h<=tot){
run(str[h]);
++h;
}
}
int main(){
read();
find();
work();
return 0;
}
有问题可在评论区留言哟。(●'◡'●)。~~~