括号配对有关问题-一道ACM在线测试题的困惑
括号配对问题--一道ACM在线测试题的困惑
昨天做了一道ACM的在线测试题目，虽然是通过了，但是对其显示的结果（所用时间和内存）有点不解。希望哪位大侠能帮忙分析分析。。。
请看原题：
描述
现在，有一行括号序列，请你检查这行括号是否配对。
输入
第一行输入一个数N（0<N<=100）,表示有N组测试数据。后面的N行输入多组输入数据，每组输入数据都是一个字符串S(S的长度小于10000，且S不是空串），测试数据组数少于5组。数据保证S中只含有"[","]","(",")"四种字符
输出
每组输入数据的输出占一行，如果该字符串中所含的括号是配对的，则输出Yes,如果不配对则输出No
样例输入
3
[(])
(])
([[]()])样例输出
No
No
Yes
下面是我的答题：运行结果显示：时间 0，内存228，长度1288
#include <stdio.h>
#include <string.h>
//当'('和')'，'['和']'个数配对时调用 返回值：0：配对成功 -1：不成功
int Peidui(char *p)
{
int xx,yy;//记录'('和‘[’的个数
char *ptmp;
ptmp=p;
while( *ptmp !='\0')
{
xx=yy=0;
if( *ptmp == '(' )
{
xx=1;
}
else if( *ptmp == '[')
{
yy=1;
}
else return -1;
if(xx) //如果第一个字符为'('
{
while((*(++ptmp) !='\0') && (xx != 0)) //直到找到配对的')'
{
if(*ptmp == '(')
xx++;
if(*ptmp == '[')
yy++;
if(*ptmp == ')') //当xx为负值时表示有')'出现在'('之前
{
xx--;
if(xx<0)
return -1;
}
if(*ptmp == ']')
{
yy--;
if(yy<0)
return -1;
}
}
if(yy) //()里面有[]不配对的情况
{
return -1;
}
}
if(yy)
{
while((*(++ptmp) !='\0')&&(yy != 0))
{
if(*ptmp == '(')
xx++;
if(*ptmp == '[')
yy++;
if(*ptmp == ')')
{
xx--;
if(xx<0)
return -1;
}
if(*ptmp == ']')
{
yy--;
if(yy<0)
return -1;
}
}
if(xx)
{
return -1;
}
}
}
return 0;
}
int main()
{
int testNum,res,i=0,j=0;
int x=0,y=0,len;
char testData[10010];
scanf("%d",&testNum);
if((testNum<=0) || (testNum>100))
return 0;
for(i=0;i<testNum;i++)
{
scanf("%s",testData);
len=strlen(testData);
if((len>=10000) && (len==0))
{
i--;
continue;
}
j=0;
while(testData[j] !='\0') //检查并记录输入的字符
{
switch(testData[j])
{
case '(':x++;break;
case ')':x--;break;
case '[':y++;break;
case ']':y--;break;
default:return 0; //不符合输入规则就退出
}
j++;
}
if(x==0 && y==0)
{
res=Peidui(testData);
if(res==0)
printf("Yes\n");
else
printf("No\n");
}
else
printf("No\n");
x=y=0; //注意这里要赋值为0
}
return 0;
}
------解决方案--------------------
可能是cin,cout的原因吧，比scanf，printf慢
“万恶的cin cout”
昨天做了一道ACM的在线测试题目，虽然是通过了，但是对其显示的结果（所用时间和内存）有点不解。希望哪位大侠能帮忙分析分析。。。
请看原题：
描述
现在，有一行括号序列，请你检查这行括号是否配对。
输入
第一行输入一个数N（0<N<=100）,表示有N组测试数据。后面的N行输入多组输入数据，每组输入数据都是一个字符串S(S的长度小于10000，且S不是空串），测试数据组数少于5组。数据保证S中只含有"[","]","(",")"四种字符
输出
每组输入数据的输出占一行，如果该字符串中所含的括号是配对的，则输出Yes,如果不配对则输出No
样例输入
3
[(])
(])
([[]()])样例输出
No
No
Yes
下面是我的答题：运行结果显示：时间 0，内存228，长度1288
#include <stdio.h>
#include <string.h>
//当'('和')'，'['和']'个数配对时调用 返回值：0：配对成功 -1：不成功
int Peidui(char *p)
{
int xx,yy;//记录'('和‘[’的个数
char *ptmp;
ptmp=p;
while( *ptmp !='\0')
{
xx=yy=0;
if( *ptmp == '(' )
{
xx=1;
}
else if( *ptmp == '[')
{
yy=1;
}
else return -1;
if(xx) //如果第一个字符为'('
{
while((*(++ptmp) !='\0') && (xx != 0)) //直到找到配对的')'
{
if(*ptmp == '(')
xx++;
if(*ptmp == '[')
yy++;
if(*ptmp == ')') //当xx为负值时表示有')'出现在'('之前
{
xx--;
if(xx<0)
return -1;
}
if(*ptmp == ']')
{
yy--;
if(yy<0)
return -1;
}
}
if(yy) //()里面有[]不配对的情况
{
return -1;
}
}
if(yy)
{
while((*(++ptmp) !='\0')&&(yy != 0))
{
if(*ptmp == '(')
xx++;
if(*ptmp == '[')
yy++;
if(*ptmp == ')')
{
xx--;
if(xx<0)
return -1;
}
if(*ptmp == ']')
{
yy--;
if(yy<0)
return -1;
}
}
if(xx)
{
return -1;
}
}
}
return 0;
}
int main()
{
int testNum,res,i=0,j=0;
int x=0,y=0,len;
char testData[10010];
scanf("%d",&testNum);
if((testNum<=0) || (testNum>100))
return 0;
for(i=0;i<testNum;i++)
{
scanf("%s",testData);
len=strlen(testData);
if((len>=10000) && (len==0))
{
i--;
continue;
}
j=0;
while(testData[j] !='\0') //检查并记录输入的字符
{
switch(testData[j])
{
case '(':x++;break;
case ')':x--;break;
case '[':y++;break;
case ']':y--;break;
default:return 0; //不符合输入规则就退出
}
j++;
}
if(x==0 && y==0)
{
res=Peidui(testData);
if(res==0)
printf("Yes\n");
else
printf("No\n");
}
else
printf("No\n");
x=y=0; //注意这里要赋值为0
}
return 0;
}
------解决方案--------------------
可能是cin,cout的原因吧，比scanf，printf慢
“万恶的cin cout”