当前位置: 代码迷 >> 其他开发语言 >> 括号配对有关问题-一道ACM在线测试题的困惑
  详细解决方案

括号配对有关问题-一道ACM在线测试题的困惑

热度:7706   发布时间:2013-02-26 00:00:00.0
括号配对问题--一道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”
探讨
引用:
用栈,如果当前括号与栈中的top匹配,栈pop,否则push当前的括号


恩,是可以。 其实我本来的问题是C和C++解同样的题,效率为什么相差这么大???
  相关解决方案