#include<iostream>
using namespace std;
char s[1000001];
int main() {
ios_base::sync_with_stdio(false);
cin>>s;
int i=0,j,n,a=0,b=0;//i是当前字符下标,j,n是临时使用的变量(后文有对其的说明),a,b分别是&,|的短路次数
bool f,d=0;//f是目前表达式的值,d为真则正在表达式短路阶段
for(;;)switch(s[i]) {
case'&':
if(d?f:s[i-1]-48)f=1,i++,d=0;
//短路时以表达式的值代表第一个操作数,否则前一项表示的数字为操作数
//仅往后一个字符,结束短路阶段
else {
f=0,a++,d=1,n=0;//&短路次数增加,短路阶段开始,括号嵌套层数n记为0(假设当前字符未在括号内)
for(j=i+1; n||j<i+2; j++)if(s[j]==40)n++;
//j为目前查找到的不处于该短路阶段的第一个字符
//因为&优先级较高,第二个操作数只能为0,1或被括起来的表达式,但不能一个字符都不接受
//当字符为'('(ASCII码40)时,嵌套层数加1
else if(s[j]==41)n--;
//当字符为')'(ASCII码41)时,嵌套层数减1
i=j;//让i跳过短路阶段
}
break;
case'|':
if(d?f:s[i-1]-48) {
f=1,b++,d=1;
for(j=i+1; (s[j]<50||n>0)&&n>=0; j++)if(s[j]==40)n++;
//在字符'0','1','(',')','&','|'中,只有'|'的ASCII码值不小于50
//(s[j]<50||n>0)&&n>=0表示,在括号含嵌套时(n>0),继续判断下一个字符;
//在括号不含嵌套时,若出现|则退出循环;
//在右括号数量大于左括号时,立即退出循环。
else if(s[j]==41)n--;
i=j;
} else f=0,i++,d=0;
break;
case 0://当字符串结束时
cout<<f<<endl<<a<<' '<<b;
return 0;
default://当为其它字符时
i++;//仅往后一个字符
}
}
当我发现第二个样例输出不对时,我就知道这题一定有WA的测试点。可测试结果 除了有AC,WA的测试点,还有好几个RE。
“电脑怎么这样不听话?”我想,“会不会是我少写了什么?”经过对代码的仔细检查,我发现,我在case'&'开关中,短路时重置了 n 的值,在case'|'中却忘了重置! 我赶忙将其加入代码,这就是我尝试的第二段代码:
#include<iostream>
using namespace std;
char s[1000001];
int main() {
ios_base::sync_with_stdio(false);
cin>>s;
int i=0,j,n,a=0,b=0;
bool f,d=0;
for(;;)switch(s[i]) {
case'&':
if(d?f:s[i-1]-48)f=1,i++,d=0;
else {
f=0,a++,d=1,n=0;
for(j=i+1; n||j<i+2; j++)if(s[j]==40)n++;
else if(s[j]==41)n--;
i=j;
}
break;
case'|':
if(d?f:s[i-1]-48) {
f=1,b++,d=1,n=0;//在此加入了n=0
for(j=i+1; (s[j]<50||n>0)&&n>=0; j++)if(s[j]==40)n++;
else if(s[j]==41)n--;
i=j;
} else f=0,i++,d=0;
break;
case 0:
cout<<f<<endl<<a<<' '<<b;
return 0;
default:
i++;
}
}
我想,这下不会再RE了吧。谁知,subtask#0中的45,48,50,51,52,subtask#1中的#5与subtask#2中的#25,#31,#32,#38,#39,#40竟一同从WA变为了RE!
算了,还是自己调试下吧。我发现,不管是哪段代码,都是在输入后先定义bool变量再定义int变量,还有时甚至把循环外的语句也当作循环体了。我真的难以置信,很会四则运算的电脑,竟然连语句的先后都会弄颠倒。