模拟（难）
给出一段程序，要求按照给定的运行方式，对每次PRINT操作判断是否有效，若有效还需求值。
并没有太多算法的题目，但各种细节很多
大致思路就是先将全部程序文本读入，进行预处理：记录每行程序的类型（赋值、打印或重置），并且
（1）如果是赋值，则对被赋值的变量进行编号，并将等号右边的内容以纯文本方式保存下来
（2）如果是打印，则检查被打印的变量之前是否存在相应赋值，若有则记录变量编号，若无则记录编号为-1
（3）如果是重置，无需特殊处理
然后就是求解了，按顺序对每行i进行处理，期间维护一个搜索赋值语句的上下界[es,ee]，初始es=ee=0，并且
（1）如果是赋值，忽略
（2）如果是打印，则ee=i-1，并尝试对该变量求值，若成功则打印值，否则打印”UNDEF”
（3）如果是重置，则es=i+1
每次对变量id求值的操作可能涉及其他变量，因此使用递归结构。而要防止循环求值，因此初始化全0数组st[]来记录变量是否在递归栈中。每次递归内部结构大致如下：
（1）若st[id]!=0，直接返回；st[id]=1，按从后往前(从ee到es)的顺序找第一个对va赋值的语句
（2）对将赋值字符串中的所有变量调用递归求值，若某变量求值失败，直接返回
（3）用一个新字符串保存将赋值字符串中所有变量替换为值后的结果（必须不修改原来的赋值字符串），随后使用递归下降分析求解该字符串的值
（4）记录变量的值，st[id]=2
最后求值完毕后，若要打印的变量st[]为2，则表示成功求值。
程序的主要部分想清楚后实现也花了不少时间，最后则是在空格问题上卡了很久。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 |
#include<cstdio> #include<cstring> #define MAXL 1000 int el,sl,st[MAXL],v[MAXL],es,ee,ti; char s[MAXL][MAXL],t[MAXL]; struct E { int ins,id; char s[MAXL]; }e[MAXL]; int exp(); int gi(int b) { int i; for(i=0;i<sl&&strcmp(s[i],t);i++); if(i==sl) { if(b) strcpy(s[sl++],t); else i=-1; } return i; } int fact() { while(t[ti]&&t[ti]==' ') ti++; int d; if(t[ti]=='(') { ti++; d=exp(); while(t[ti]!=')') ti++; ti++; return d; } sscanf(t+ti,"%d",&d); if(t[ti]&&t[ti]=='-') ti++; while(t[ti]&&t[ti]>='0'&&t[ti]<='9') ti++; return d; } int term() { while(t[ti]&&t[ti]==' ') ti++; int d=fact(); while(t[ti]) { while(t[ti]&&t[ti]==' ') ti++; if(!t[ti]||t[ti]!='*') break; ti++; d*=fact(); } return d; } int exp() { while(t[ti]&&t[ti]==' ') ti++; int d=term(); while(t[ti]) { while(t[ti]&&t[ti]==' ') ti++; if(!t[ti]||t[ti]!='+'&&t[ti]!='-') break; ti++; if(t[ti-1]=='+') d+=term(); else d-=term(); } return d; } void vl(int id) { if(st[id]!=0) return; st[id]=1; int i,j,k,rl; char r[MAXL]; for(i=ee-1;i>=es;i--) { if(e[i].ins==1&&e[i].id==id) break; } if(i<es) return; memset(r,0,sizeof r); for(j=rl=0;e[i].s[j];) { if(e[i].s[j]=='('||e[i].s[j]==')'||e[i].s[j]==' '|| e[i].s[j]=='+'||e[i].s[j]=='-'||e[i].s[j]=='*') { r[rl++]=e[i].s[j++]; } else if(e[i].s[j]=='-'||e[i].s[j]>='0'&&e[i].s[j]<='9') { r[rl++]=e[i].s[j++]; while(e[i].s[j]&&e[i].s[j]>='0'&&e[i].s[j]<='9') { r[rl++]=e[i].s[j++]; } } else { for(k=j;e[i].s[k]>='a'&&e[i].s[k]<='z' ||e[i].s[k]>='A'&&e[i].s[k]<='Z' ||e[i].s[k]>='0'&&e[i].s[k]<='9';k++) t[k-j]=e[i].s[k]; t[k-j]=0; k=gi(0); if(k==-1) return; vl(k); if(st[k]!=2) return; sprintf(r+rl,"%d",v[k]); while(r[rl]) rl++; while(e[i].s[j]&&(e[i].s[j]>='a'&&e[i].s[j]<='z' ||e[i].s[j]>='A'&&e[i].s[j]<='Z' ||e[i].s[j]>='0'&&e[i].s[j]<='9')) j++; } } memcpy(t,r,sizeof t); ti=0; v[id]=exp(); st[id]=2; } void init() { while(~scanf("%s",t)) { if(!strcmp(t,"PRINT")) { e[el].ins=2; scanf("%s",t); e[el].id=gi(0); } else if(!strcmp(t,"RESET")) { e[el].ins=3; } else { for(ti=1;t[ti]&&!(t[ti-1]==':'&&t[ti]=='=');ti++); if(!t[ti]) { e[el].ins=1; e[el].id=gi(1); scanf("%s",t); if(!strcmp(t,":=")) gets(e[el].s); else strcpy(e[el].s,t+2); } else { strcpy(e[el].s,t+ti+1); t[ti-1]=0; e[el].ins=1; e[el].id=gi(1); } } el++; } } void solve() { int i; for(i=0;i<el;i++) { if(e[i].ins==2) { if(e[i].id==-1) { puts("UNDEF"); continue; } memset(st,0,sizeof st); ee=i; vl(e[i].id); if(st[e[i].id]<2) puts("UNDEF"); else printf("%d\n",v[e[i].id]); } else if(e[i].ins==3) { es=i+1; } } } int main() { init(); solve(); return 0; } |
在POJ上做过最冷门的题目了，算上我也才53个人AC。但貌似数据比较弱哦，总觉得比想象中要顺利得多……