此题是非常典型的表达式求值问题，既然只有最多15个变量，那就枚举每一种变量的取值代入计算，如果全部相等则认为两个表达式相等。
View Code 1 #include2 3 char ve[500][50]; 4 long x[500],vnum,pfs,pf; 5 6 int tran(char c){ 7 8 if (c==')') 9 return 0; 10 11 if (c=='^') 12 return 1; 13 14 if (c=='|') 15 return 2; 16 17 if (c=='&') 18 return 3; 19 20 if (c=='!') 21 return 4; 22 23 if (((c<='z')&&(c>='a'))||((c<='Z')&&(c>='A'))) 24 return 7; 25 26 return -1; 27 } 28 29 long cal(long z[],long pz,long r[],long pr){ 30 31 if (z[pz]==4){ 32 33 r[pr]=!r[pr]; 34 return pr; 35 } 36 37 if (z[pz]==3){ 38 39 r[pr-1]=r[pr]&r[pr-1]; 40 return pr-1; 41 } 42 43 if (z[pz]==2){ 44 45 r[pr-1]=r[pr]|r[pr-1]; 46 return pr-1; 47 } 48 49 if (z[pz]==1) { 50 51 r[pr-1]=r[pr]^r[pr-1]; 52 return pr-1; 53 } 54 55 return pr; 56 } 57 58 long finds(char s[],long p,long max){ 59 60 char ss[50]; 61 long i,j,j1,w; 62 63 for (i=0;(i<=max)&&(tran(s[p])==7);i++,p++){ 64 65 ss[i]=s[p]; 66 } 67 pfs=p-1; 68 69 ss[i]=0; 70 71 for (j=1;j<=vnum;j++){ 72 73 w=0; 74 75 for (j1=0;ss[j1]==ve[j][j1];j1++){ 76 77 if (ss[j1]==0){ 78 79 w=1; 80 break; 81 } 82 } 83 84 if (w){ 85 86 return x[j]; 87 } 88 89 } 90 91 92 return -1; 93 } 94 95 long find(char s[],long p,long max){ 96 97 long zo[5000],zn[5000],on,nn,i,j; 98 99 on=0; 100 nn=0; 101 102 zn[0]=0; 103 zo[0]=-1; 104 105 for (i=p;i<=max;i++){ 106 107 if (s[i]=='('){ 108 109 nn++; 110 zn[nn]=find(s, i+1,max); 111 i=pf; 112 113 continue; 114 } 115 116 j=tran(s[i]); 117 118 if (j==7){ 119 120 nn++; 121 zn[nn]=finds(s,i,max); 122 i=pfs; 123 124 continue; 125 } 126 127 if ((j>=0)&&(j<=4)){ 128 129 while (zo[on]>j){ 130 131 nn=cal(zo, on, zn, nn); 132 on--; 133 } 134 135 on++; 136 zo[on]=j; 137 138 if (j==0){ 139 140 pf=i; 141 142 return zn[nn]; 143 } 144 } 145 } 146 147 pf=i; 148 return 0; 149 } 150 151 int main (){ 152 153 char s1[5000],s2[5000]; 154 long i,j,l1,l2,k,le,re1,re2,relast; 155 156 while (1){ 157 158 i=1; 159 if (scanf("%c",s1+i)==EOF) 160 break; 161 162 if (s1[i]=='\n'){ 163 164 break; 165 } 166 else{ 167 168 while (s1[i]!='\n'){ 169 170 i++; 171 if (scanf("%c",s1+i)==EOF) 172 return 0; 173 } 174 } 175 176 l1=i; 177 s1[l1]=')'; 178 s1[0]='('; 179 180 i=1; 181 if (scanf("%c",s2+i)==EOF) 182 return 0; 183 184 while (s2[i]!='\n'){ 185 186 i++; 187 if (scanf("%c",s2+i)==EOF) 188 return 0; 189 } 190 191 l2=i; 192 193 s1[0]='('; 194 s2[l2]=')'; 195 196 vnum=0; 197 198 for (i=0;i<=l1;i++){ 199 200 if (((s1[i]<='z')&&(s1[i]>='a'))||((s1[i]<='Z')&&(s1[i]>='A'))){ 201 202 vnum++; 203 for (j=0;((s1[i]<='z')&&(s1[i]>='a'))||((s1[i]<='Z')&&(s1[i]>='A'));j++,i++){ 204 205 ve[vnum][j]=s1[i]; 206 } 207 208 ve[vnum][j]=0; 209 } 210 } 211 212 relast=1; 213 214 for (k=0;;k++){ 215 216 le=k; 217 218 for (i=1;i<=vnum;i++){ 219 220 x[i]=le%2; 221 le=le/2; 222 } 223 224 if (le) 225 break; 226 227 re1=find(s1,1,l1); 228 re2=find(s2,1,l2); 229 230 if (re1!=re2){ 231 232 relast=0; 233 break; 234 235 } 236 } 237 238 if (relast==1){ 239 240 printf("TRUE\n"); 241 } 242 else{ 243 244 printf("FALSE\n"); 245 } 246 247 } 248 return 0; 249 }