主题：第49次编程比赛题目
neverPE [专家分：1620] 发布于 2007-02-23 20:11:00
题目：给出一个包含各种括号的表达式，判断括号是否配对。括号配对的条件：括号必须先左后右，并且左右括号数量相等；对于多重括号，从外到内嵌套顺序为：{} -> [] -> () -> <>。例如{[(<>)]}。
接口： bool match(char* str); 合法返回true， 否则返回false。
输入范例：
{[(<>)]}
{}
<(>)
<()>
返回：
true
true
false
false
大过年的， 也不能让大家累着：）这次的题目相对来说很简单，容易理解，容易上手，容易做对。 但牛人们还是有发挥的余地， 速度最快并不容易。
结束时间：下周一中午12点，结束前本帖隐藏回复。 有任何问题另外开帖询问，或者参考以前的规则。
最后更新于：2007-02-23 20:16:00
回复列表 （共33个回复）
31 楼
ghbxx2004 [专家分：610] 发布于 2007-02-26 12:01:00
#include "stdio.h"
typedef int bool;
#define true 1
#define false 0
char symbol[8]={'{','[','(','<','>',')',']','}'};
char number[100000000];
bool match(char *str)/*这个函数的条件是字符串的结束有结束符\0*/
{
bool result=true;;
long i;
long pleft,pright;
char *left,*right;
left=str;
pleft=0;
while(pleft<=3)
{
while(*left!=symbol[pleft]&&(pleft<8)){pleft++;}
left++;
}
if(pleft>=8){result=false;goto next;}
else
{
right=left-1;
left=left-2;
pleft=3;pright=4;
while(left!=str)
{
while(symbol[pleft]!=*left&&(pleft>0)){pleft--;}
while(symbol[pright]!=*right&&(pright<8)){pright++;}
if(3-pleft!=pright-4){result=false;goto next;}
left--;right++;
}
while(symbol[pleft]!=*left&&(pleft>0)){pleft--;}
while(symbol[pright]!=*right&&(pright<8)){pright++;}
if(3-pleft!=pright-4){result=false;goto next;}
else{if(*(++right)!='\0'){result=false;goto next;}}
}
next:
return result;
}
int main()
{
char c;
long i=0;
while((c=getchar())!='\n'){number[i++]=c;}
number[i]='\0';
if(match(number)==true){printf("true");}
else{printf("false");}
return 0;
}
在DEV—CPP下编译通过
32 楼
ITER [专家分：680] 发布于 2007-02-26 12:12:00
终于又有比赛了哈 呵呵
好9没来看了 貌似比赛又在进行了
因为11点40才看到 所以匆匆编好也没怎么测试 ：）
其中对题意不是很了解 比如<<>>是否可以 不是很清楚
由于题目上也没说可以，所以在此程序中做“不可以”处理
#include <iostream>
using namespace std;
int compair(char a,char b)
{
if('<'==a)
return 0;//假设<>内不能再嵌套其他括号
if('('==a)
{
if('<'==b)
return 1;
else return 0;
}
else
{
if(a>b)
return 1;
else return 0;
}
}
bool match(char* str)
{
char zhan[20];
int top(0);
int xiabiao(0);
int length = strlen(str);
zhan[top++] = str[xiabiao++];
while(xiabiao<length)
{
char tmp = str[xiabiao];
if(0==top)
{
zhan[top++] = tmp;
}
else if('{'==tmp||'['==tmp||'('==tmp||'<'==tmp)
{
if(compair(zhan[top-1],tmp))
{
zhan[top++] = tmp;
}
else return false;
}
else
{
if(tmp-zhan[top-1]<3)
{
top--;
}
else return false;
}
xiabiao++;
}
if(0==top)
return true;
else return false;
}
main()
{
char enter[16];
cin>>enter;
cout<<match(enter);
}
33 楼
neverPE [专家分：1620] 发布于 2007-02-26 12:14:00
时间到。 谢谢各位捧场。
我来回复
您所在位置：