主题：第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个回复）
11 楼
我不太会 [专家分：0] 发布于 2007-02-24 02:33:00
#include<cstring>
#include<cmath>
using namespace std;
bool match(char* str)
{
int length=strlen(str);
if(length%2)
{
return false;
}
int i=length/2-1;
int j;
for(j=i;j>0;j--)
{
if((str[j]!='<'&&str[j-1]!='<'&&str[j]>str[j-1])||(str[i]!='<'&&str[i-1]=='<')||
(str[length-j-1]!='>'&&str[length-j]!='>'&&str[length-j-1]>str[length-j])||
(str[length-j-1]!='>'&&str[length-j]=='>'))
{
return false;
}
if(abs(str[j]-str[length-j-1])!=2&&abs(str[j]-str[length-j-1])!=1)
{
return false;
}
}
if(abs(str[j]-str[length-j-1])!=2&&abs(str[j]-str[length-j-1])!=1)
{
return false;
}
return true;
}
12 楼
eastcowboy [专家分：25370] 发布于 2007-02-24 11:03:00
/* 判断括号是否配对
* 规定括号的大小顺序：{}, [], (), <>，
* 其中大的括号可以包含小的括号，而小的括号不能包含大的括号
* 由于题目没有明确叙述，默认同级括号可以嵌套，即(())算作合法配对
* 对于空字符串，认为其本身就是配对的
*
* 思路：使用两个堆栈
* 一个堆栈保存字符，用来判断同级括号是否配对
* 一个堆栈保存状态，用来判断当前括号是否允许出现
*
* 编程语言：C++
* 调试环境：Visual Studio 2005
*/
#define push(c, s) \
do{ \
CharStack[tos] = c; \
StatStack[tos] = s; \
++tos; \
}while(0)
bool match(char* str)
{
const int STACK_SIZE = 1000;
char* CharStack = new char[STACK_SIZE];
int* StatStack = new int[STACK_SIZE];
int tos = 0;
for(; *str != '\0'; ++str)
{
switch(*str)
{
case '{':
if( tos != 0 )
if( (StatStack[tos-1] & 0x08) == 0 )
goto end;
push('{', 0x0F);
break;
case '[':
if( tos != 0 )
if( (StatStack[tos-1] & 0x04) == 0 )
goto end;
push('[', 0x07);
break;
case '(':
if( tos != 0 )
if( (StatStack[tos-1] & 0x02) == 0 )
goto end;
push('(', 0x03);
break;
case '<':
push('<', 0x01);
break;
case '}':
if( tos == 0 || CharStack[tos-1] != '{' )
goto end;
--tos;
break;
case ']':
if( tos == 0 || CharStack[tos-1] != '[' )
goto end;
--tos;
break;
case ')':
if( tos == 0 || CharStack[tos-1] != '(' )
goto end;
--tos;
break;
case '>':
if( tos == 0 || CharStack[tos-1] != '<' )
goto end;
--tos;
break;
break;
}
}
end:
delete[] CharStack;
delete[] StatStack;
return *str == 0 && tos == 0;
}
// 以下为测试用的代码
#include <iostream>
using namespace std;
int main()
{
char* str_list[] =
{
// 题目给出的测试用例
"{[(<>)]}", // true
"{}", // true
"<(>)", // false
"<()>", // false
// 自己的测试用例
"", // true
"{[][]()<>(<>)}{()}", // true
"{[][]()<>(<>)(}", // false
"{[][]()<>(<>)}{<()>}", // false
// 结束标志
0
};
for(int i = 0; str_list[i] != 0; ++i)
cout << i+1 << '\t' << (match(str_list[i])?"true":"false") << endl;
return 0;
}
13 楼
dongdong123 [专家分：0] 发布于 2007-02-24 11:05:00
vs2005 环境
// Stack_BracketMatch.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <string>
#include<iostream>
#include<stack>
using namespace std;
bool match(char*); //接口函数定义
char corresbondingBracket(char orig_brac);//返回对应符号用于判断
int _tmain(int argc, _TCHAR* argv[])
{
char*CStr="{}";
char*CStr1="<(>)";
char*CStr2="{[(<>)]}";
std::cout <<match(CStr)<<std::endl
<<match(CStr1)<<std::endl
<<match(CStr2)<<std::endl;
system("pause");
return 0;
}
bool match(char*charArr)
{
string str=charArr;
const char*charArr2;
stack<char>charStack;//栈结构保存括号
charStack.push(str[0]);
for( unsigned int i=0;i<str.length();i++)
{
if((str[i+1])==corresbondingBracket(str[i]))
{
charStack.pop();
str.erase(i,2);
charArr2=str.c_str ();
bool match(charArr2);
i=-1;
}
else{
charStack.push(str[i+1]);
}//else
} //for
//return charStack.empty();
if(str.empty())
/* if(str.empty())
{
以上没有考虑次序问题
实在太困拉 在此给出思路
此时是括号匹配 只需取一半
若没有右边括好 便按设置的优先级
入栈 弹栈 操作 栈为空时
返回true 否则 返回false
}*/
return true;
else return false;
}
char corresbondingBracket(char orig_brac)
{
switch(orig_brac)
{
case'(' :
return')'; break;
case')':
return'('; break;
case'[':
return ']'; break;
case']':
return '['; break;
case'{':
return '}'; break;
case'}':
return '{'; break;
case'<':
return '>'; break;
case'>':
return '<'; break;
default: return '#';
}
}
14 楼
55560380 [专家分：30] 发布于 2007-02-24 11:19:00
我也来写一个
#include <stdio.h>
#include <ctype.h>
int match(char* str)
{
int i;
int p;
int temp=strlen(str);
p=temp-1;
if (temp % 2 != 0)
return 0;
else
{
for (i=0; i<temp/2; ++i)
{
if ( (*(str+i) == *(str+p-i)-2) || (*(str+i) == *(str+p-i)-1) )
continue;
else
return 0;
}
}
return 1;
}
int match (char* str);
int main(void)
{
char *p[2]={"{[<()>]}","<(>)"};
int temp=0;
for ( ; temp<2; ++temp)
{
if (match(p[temp]))
printf("yes\n");
else
printf("no\n");
}
return 0;
}
15 楼
bloodybg [专家分：1510] 发布于 2007-02-24 11:25:00
bool match(char *str)
{
char *p = str;
char a1, a2 = 5;
long count = 0;
while (NULL != *p)
{
switch(*p)
{
case '{':
a1 = 4;
break;
case '}':
a1 = -4;
break;
case '[':
a1 = 3;
break;
case ']':
a1 = -3;
break;
case '(':
a1 = 2;
break;
case ')':
a1 = -2;
break;
case '<':
a1 = 1;
break;
case '>':
a1 = -1;
break;
default:
continue;
}
if (a1 > a2)
return false;
count += a1;
if (0 > count)
return false;
a2 = a1;
p ++;
}
return 0 == count ? true : false;
}
16 楼
iAkiak [专家分：8460] 发布于 2007-02-24 12:48:00
#include <cassert>
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
enum Flag
{
F_Left = 1 << 2,
F_Right = 2 << 2,
F_Mask = F_Left | F_Right,
F_PriMask = 0x03,
};
bool match(char* str)
{
assert(str);
static char flag[256] = {0};
static bool inited = false;
if (!inited)
{
flag['{'] = F_Left | 0;
flag['['] = F_Left | 1
flag['('] = F_Left | 2;
flag['<'] = F_Left | 3;
flag['}'] = F_Right | 0;
flag[']'] = F_Right | 1;
flag[')'] = F_Right | 2;
flag['>'] = F_Right | 3;
inited = true;
}
for(stack<char> s; *str; str++)
{
const char f = flag[(unsigned char)*str];
if (!f)
continue;
const char priority = f & F_PriMask;
if ((f & F_Mask) == F_Left)
{
if (!s.empty() && s.top() > priority)
return false;
s.push(priority);
}
else //if ((f & F_Mask) == F_Right)
{
if (s.empty() || s.top() != priority)
return false;
s.pop();
}
}
return true;
}
int main()
{
char s[128];
while(scanf("%s", s) == 1)
{
printf("%s\n", match(s)?"true":"false");
}
return 0;
}
17 楼
rj1985 [专家分：20] 发布于 2007-02-24 13:23:00
//接口函数 int match(char* str);
//返回值： 1=true; 0=false
int match(char* str)
{
int i,n,count;
int s[]={0,0,0,0,0}; //保存每个嵌套层次的括号类型
char mode[5]={'\0','}',']',')','>'};
char c;
count=0; //记录当前嵌套层数
n=0; //最内层括号优先级
i=0; //外一层括号优先级
do
{
c=*str++;
switch(c) //确定当前括号优先级
{
case '{':n=1;break;
case '[':n=2;break;
case '(':n=3;break;
case '<':n=4;break;
default:n=0;break;
}
if (n==0 && c!='}' && c!=']' && c!=')' && c!='>') continue; //当前字符不为括号时跳过
if (n>i) //当前括号优先级低于前一个和括号，嵌套加1
{
s[++count]=n; //保存括号类型
i=n;
}
else
{
if (n!=0 || c!=mode[i])
{
return 0; //不配对，返回0，即false
}
else
{
i=s[--count]; //配对，嵌套层数-1
}
}
}while(*str);
if (count) return 0; //所有括号成对出现，则正确
else return 1;
}
int main()
{
char a[]={"{[<>()]}"};
cout<<"1111: "<<match(a)<<endl;
}
18 楼
hj36277 [专家分：130] 发布于 2007-02-24 17:36:00
#include<iostream.h>
class Lcll
{
Lcll* next,*down;
char x;
public:
Lcll(char xx='\0',Lcll* next1=NULL,Lcll* down1=NULL)
{
next=next1;
x=xx;
down=down1;
}
bool Getmatch(char xx)
{
if('<'==xx)
return true;
if('('==xx)
{
if('('==this->down->x||'<'==this->down->x)
return true;
return false;
}
if('['==xx)
{
if(this->down->x>=91)
return true;
return false;
}
if('{'==this->down->x)
return true;
return false;
}
bool match(char* str)
{
Lcll* p;
while(*str)
{
if('{'==(*str)||'['==(*str)||'('==(*str)||'<'==(*str))
{
if(this->down)
{
if(!Getmatch(*str))
return false;
p=new Lcll(*str,NULL,this->down);
this->down->next=p;
this->down=p;
}
else
{
this->down=new Lcll(*str,NULL,this);
this->next=this->down;
}
}
if(')'==(*str))
{
if('('!=this->down->x)
return false;
p=this->down->next;
delete this->down;
this->down=p;
}
if('}'==(*str)||']'==(*str)||'>'==(*str))
{
if(*str!=(this->down->x)+2)
return false;
p=this->down->next;
delete this->down;
this->down=p;
}
str++;
}
if((this->next))
return false;
return true;
}
void printf(char* str)
{
if(match(str))
cout<<"对"<<endl;
else
cout<<"错"<<endl;
}
~Lcll()
{
Lcll* p=this->down;
while(p)
{
this->down=this->down->down;
delete p;
p=this->down;
}
}
};
int main()
{
Lcll p;
char a[200];
cin>>a;
p.printf(a);
return 1;
}
帮我看下 为什么输入对的时候不显示字 谢谢了
19 楼
xchbcahz [专家分：50] 发布于 2007-02-24 18:39:00
//请大家多多指教！
bool match(char* str)
{
if(str==null)
return false;
char* p=str;
int s0=0,s1=0,s2=0,s3=0; //分别代表{}、[]、()、<>的计数;
while(*p!='\0')
{
switch(*p)
{
case '{':
if(s1>0||s2>0||s3>0)
return false;
else s0++;
break;
case '[':
if(s2>0||s3>0)
return false;
else s1++;
break;
case '(':
if(s3>0)
return false;
else s2++;
break;
case '<':
s3++;
break;
case '>':
if(s3<1)
return false;
else
s3--;
break;
case ')':
if(s2<1||s3>0)
return false;
else
s2--;
break;
case ']':
if(s1<1||s2>0||s3>0)
return false;
else
s1--;
break;
case '}':
if(s0<1||s1>0||s2>0||s3>0)
return false;
else
s0--;
break;
}
p++;
}
if(s0!=0||s1!=0||s2!=0||s3!=0)
return false;
else
return true;
}
20 楼
crossbow [专家分：150] 发布于 2007-02-24 20:03:00
//try my luck
#include <stack>
bool match(char *str)
{
std::stack<char> stk;
while(*str != '\0')
{
switch(*str++)
{
case '{':
{
if(stk.empty())
{
stk.push('{');
}
else
{
return false;
}
break;
}
case '}':
{
if(!stk.empty() && stk.top() == '{')
{
stk.pop();
}
else
{
return false;
}
break;
}
case '[':
{
if(stk.empty() || stk.top() == '{')
{
stk.push('[');
}
else
{
return false;
}
break;
}
case ']':
{
if(!stk.empty() && stk.top() == '[')
{
stk.pop();
}
else
{
return false;
}
break;
}
case '(':
{
if(stk.empty() || stk.top() == '{' || stk.top() == '[')
{
stk.push('(');
}
else
{
return false;
}
break;
}
case ')':
{
if(!stk.empty() && stk.top() == '(')
{
stk.pop();
}
else
{
return false;
}
break;
}
case '<':
{
if(stk.empty() || stk.top() != '<')
{
stk.push('<');
}
else
{
return false;
}
break;
}
case '>':
{
if(!stk.empty() && stk.top() == '<')
{
stk.pop();
}
else
{
return false;
}
break;
}
default:
{
return false;
}
}
}
return stk.empty();
}
我来回复
您所在位置：