主题：第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个回复）
沙发
neverPE [专家分：1620] 发布于 2007-02-23 20:12:00
test
板凳
redraiment [专家分：290] 发布于 2007-02-23 21:33:00
本人初次来，不懂这里的规矩。
代码直接贴出来？
这个题意还不是很了解。是不是最多只能套四层？我现在是这么理解。
(())
我就判断它错了。
{[][]}
判断它对。
代码已经写好了，贴？还是不贴？
3 楼
redraiment [专家分：290] 发布于 2007-02-23 21:34:00
#include <stdio.h>
int bracket[4] = {0};
int match(char *str)
{
register int i;
for (i = 0 ; str[i] ; i++)
{
switch (str[i])
{
case '{':
if (bracket[0] || bracket[1] || bracket[2] || bracket[3])
return 1;
bracket[0]++;
break;
case '}':
bracket[0]--;
if (bracket[0] < 0)
return 1;
break;
case '[':
if (bracket[1] || bracket[2] || bracket[3])
return 1;
bracket[1]++;
break;
case ']':
bracket[1]--;
if (bracket[1] < 0)
return 1;
break;
case '(':
if (bracket[2] || bracket[3])
return 1;
bracket[2]++;
break;
case ')':
bracket[2]--;
if (bracket[2] < 0)
return 1;
break;
break;
case '<':
if (bracket[3])
return 1;
bracket[3]++;
break;
case '>':
bracket[3]--;
if (bracket[3] < 0)
return 1;
break;
break;
default:
return 1;
break;
}
}
return bracket[0] || bracket[1] || bracket[2] || bracket[3]?1:0;
}
int main(void)
{
char bra[256];
while (scanf("%s", bra)!=EOF)
{
if (match(bra))
printf("false\n");
else
printf("true\n");
}
}
4 楼
skybtone [专家分：160] 发布于 2007-02-23 21:36:00
#include <stdio.h>
#include <string.h>
#include <malloc.h>
typedef char SElemType; //指定char为栈的元素类型
typedef struct {
SElemType *base;
SElemType *top;
int stacksize;
} SqStack;
# define STACK_INIT_SIZE 100
# define STACKINCREMENT 10
bool InitStack (SqStack &S){
S.base=(SElemType *)malloc(STACKINCREMENT*sizeof(SElemType));
if (!S.base) return false;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return true;
}
bool DestroyStack (SqStack &S){
free (S.top);
free (S.base);
S.top=S.base=NULL;
S.stacksize=0;
return true;
}
bool StackEmpty(SqStack &S){
if (S.base==S.top) return true;
else return false;
}
bool GetTop(SqStack S,SElemType &e){
if (S.top==S.base) return false; // 空栈
e = *(S.top-1);
return true;
}
bool Push (SqStack &S, SElemType e){
if (S.top-S.base==S.stacksize) // 栈满 追加存储空间
{
S.base=(SElemType*)realloc(S.base, (S.stacksize+STACKINCREMENT)*sizeof(SElemType));
if (!S.base) return false;
S.top=S.base+S.stacksize; // top此时应该在的位置
S.stacksize+=STACKINCREMENT;
};
*S.top = e; S.top++;
return true;
}
bool Pop (SqStack &S, SElemType &e){
if (S.top==S.base) return false;
S.top --; e = *S.top;
return true;
}
bool match(char* str){
char kuohu,temp;
SqStack S_kuohu;
InitStack (S_kuohu);
do {
kuohu=*str;
if ( kuohu== '<'||kuohu== '('||kuohu== '['||kuohu== '{' ){
if (!StackEmpty(S_kuohu)){
GetTop(S_kuohu,temp);
switch(kuohu)
{
case '<':break;
case '(':
if( temp == '<')return false;else break;
case '[':
if( temp == '<'||temp=='(')return false;else break;
case '{':
if( temp== '<'|| temp== '('|| temp== '[')return false;else break;
default:break;
}
}
Push(S_kuohu,kuohu) ; //不论什么左括号，统一先入栈
}
else if (kuohu=='>') // 当读入右圆时要单独处理，它只和栈顶的左尖括号匹配
{
if (StackEmpty(S_kuohu)) return false; //栈若空，表示缺少左括弧与当前的右圆括弧匹配，返回错误
Pop (S_kuohu,temp); // 弹出栈顶元素，即当前最急切匹配的左括弧，暂存到变量temp中
if (temp!='<') return false; //如果当前最急切匹配的不是左圆括弧，则返回错误
}
else if (kuohu==')'){
if (StackEmpty(S_kuohu)) return false;
Pop (S_kuohu,temp);
if (temp!='(') return false;
}
else if(kuohu==']'){
if (StackEmpty(S_kuohu))return false;
Pop (S_kuohu,temp);
if (temp!='[') return false;
}
else if(kuohu=='}'){
if (StackEmpty(S_kuohu)) return false;
Pop (S_kuohu,temp);
if (temp!='{') return false;
};
++str;
}while (kuohu!='\0'); //结束标记 读到结束符号，表示括弧序列完毕
if (StackEmpty(S_kuohu)) return true ; //若括弧序列处理完毕，栈回到空的状态，表示所有左右括弧匹配消解完毕，返回正确
else return false; // 若括弧序列处理完毕时，栈非空，还有未消解掉的左括弧在栈中，返回错误
}
int main()
{
if (match("{[<()>]}")) printf ("\n 括弧序列是匹配的\n");
else printf ("\n 括弧序列不匹配\n");
return 0;
}
5 楼
euc [专家分：4310] 发布于 2007-02-23 22:33:00
#include <stack>
using namespace std;
class bracket {
public:
bracket () {
memset (_table, 0, sizeof (_table));
_table['{'] = 1, _table['['] = 2, _table['('] = 3, _table['<'] =4;
_table['}'] = 15, _table[']'] = 16, _table[')'] = 17, _table['>'] =18;
}
~bracket () {}
public:
bool isbracket (char c) {return _table[c] != 0;}
bool match (char *str);
private:
unsigned char _table[128];
};
bool bracket::match (char *str)
{
stack< char > stk;
for (char *p = str; *p; ++p) {
if (isbracket (*p)) {
int lvlp = _table[*p];
int lvlt;
if (stk.empty ()) {
stk.push (*p);
continue;
}
else
lvlt = _table[stk.top ()];
if ((unsigned)(*p - stk.top ()) <= 2)
stk.pop ();
else if (lvlt <= 4 && lvlp <= 4 && lvlp > lvlt)
stk.push (*p);
else
return false;
}
}
return stk.empty ();
}
bool match (char *str)
{
static bracket brk;
return brk.match (str);
}
没有自信,唉...
6 楼
bpttc [专家分：8790] 发布于 2007-02-23 22:49:00
/*------------------------------------------------------------------------*/
/* 给出一个包含各种括号的表达式，判断括号是否配对。 */
/* 括号配对的条件：括号必须先左后右，并且左右括号数量相等； */
/* 对于多重括号，从外到内嵌套顺序为：{} -> [] -> () -> <> 例如{[(<>)]} */
/* 接口： Bool match(const char* str); 合法返回True， 否则返回False。 */
/*------------------------------------------------------------------------*/
#include <stdlib.h>
#define GET_PRJ(X) ((X) + (((~(X)) & 4) << 3)) //获得左括号优先级
typedef int Bool;
#define TRUE ( 1 )
#define FALSE ( 0 )
Bool match(const char* str)
{
char *stack = NULL; //栈
int top; //栈顶指针
int len_str; //字符串长度
int i;
for (len_str = 0; '\0' != str[len_str]; ++len_str)
; //取得字符串长度
//初始化栈
stack = (char*)malloc(len_str * sizeof(char));
if (NULL == stack)
{
exit(1);
}
top = -1;
//开始分析字串
for (i=0; i < len_str; ++i)
{
switch (str[i])
{
case '<': case '(': case '[': case '{':
if ((top < 0) || (GET_PRJ(str[i]) < GET_PRJ(stack[top])))
{//判断左括号是否合法
stack[++top] = str[i];
}
else
{
free(stack);
return FALSE;
}
break;
case '>': case ')': case ']': case '}':
if ((top < 0) || (str[i] - stack[top] < 0)
|| (str[i] - stack[top] > 2))
{//判断右括号是否非法
free(stack);
return FALSE;
}
else
{
--top;
}
break;
default:
;
break;
}//end switch
}//end for
if (top < 0)
{
free(stack);
return TRUE;
}
else
{//若栈中有残留，说明右括号失配
free(stack);
return FALSE;
}
}
7 楼
bpttc [专家分：8790] 发布于 2007-02-23 23:32:00
不好意思 刚才发的太急了 忘了参数的判断 上面的作废
/*------------------------------------------------------------------------*/
/* 给出一个包含各种括号的表达式，判断括号是否配对。 */
/* 括号配对的条件：括号必须先左后右，并且左右括号数量相等； */
/* 对于多重括号，从外到内嵌套顺序为：{} -> [] -> () -> <> 例如{[(<>)]} */
/* 接口： Bool match(const char* str); 合法返回True， 否则返回False。 */
/*------------------------------------------------------------------------*/
#include <stdlib.h>
#define GET_PRJ(X) ((X) + (((~(X)) & 4) << 3)) //获得左括号优先级
typedef int Bool;
#define TRUE ( 1 )
#define FALSE ( 0 )
Bool match(const char* str)
{
char *stack = NULL; //栈
int top; //栈顶指针
int len_str; //字符串长度
int i;
if (NULL == str)
{
return FALSE;
}
for (len_str = 0; '\0' != str[len_str]; ++len_str)
; //取得字符串长度
//初始化栈
stack = (char*)malloc(len_str * sizeof(char));
if (NULL == stack)
{
exit(1);
}
top = -1;
//开始分析字串
for (i=0; i < len_str; ++i)
{
switch (str[i])
{
case '<': case '(': case '[': case '{':
if ((top < 0) || (GET_PRJ(str[i]) < GET_PRJ(stack[top])))
{//判断左括号是否合法
stack[++top] = str[i];
}
else
{
free(stack);
return FALSE;
}
break;
case '>': case ')': case ']': case '}':
if ((top < 0) || (str[i] - stack[top] < 0)
|| (str[i] - stack[top] > 2))
{//判断右括号是否非法
free(stack);
return FALSE;
}
else
{
--top;
}
break;
default:
;
break;
}//end switch
}//end for
if (top < 0)
{
free(stack);
return TRUE;
}
else
{//若栈中有残留，说明失配
free(stack);
return FALSE;
}
}
8 楼
mj_159357 [专家分：0] 发布于 2007-02-24 00:31:00
是不是要用到 栈 啊?
9 楼
codedog [专家分：60] 发布于 2007-02-24 00:33:00
bool match(char* str)
{
stack<char> CheckStack;
bool IsMatch = true;
const int len = strlen(str); // 表达式的长度
for(int i=0;i<len;i++)
{
if(!IsMatch) // 一旦判定括号不匹配即跳出循环
{
break;
}
switch(str[i])
{
case '{':
if(!CheckStack.empty())
{
if(CheckStack.top() == '[' || CheckStack.top() == '(' || CheckStack.top() == '<')
{
IsMatch = false;
break;
}
}
CheckStack.push(str[i]);
break;
case '[':
if(!CheckStack.empty())
{
if(CheckStack.top() == '(' || CheckStack.top() == '<')
{
IsMatch = false;
break;
}
}
CheckStack.push(str[i]);
break;
case '(':
if(!CheckStack.empty())
{
if(CheckStack.top() == '<')
{
IsMatch = false;
break;
}
}
CheckStack.push(str[i]);
break;
case '<':
CheckStack.push(str[i]);
break;
case '>':
if(!CheckStack.empty() && CheckStack.top() == '<')
{
CheckStack.pop(); // 栈顶的左尖括号出栈
}
else
{
IsMatch = false;
}
break;
case ')':
if(!CheckStack.empty() && CheckStack.top() == '(')
{
CheckStack.pop(); // 栈顶的左圆括号出栈
}
else
{
IsMatch = false;
}
break;
case ']':
if(!CheckStack.empty() && CheckStack.top() == '[')
{
CheckStack.pop(); // 栈顶的左方括号出栈
}
else
{
IsMatch = false;
}
break;
case '}':
if(!CheckStack.empty() && CheckStack.top() == '{')
{
CheckStack.pop(); // 栈顶的左大括号出栈
}
else
{
IsMatch = false;
}
break;
default:
break;
}
}
if(!CheckStack.empty())
{
IsMatch = false;
}
return IsMatch;
}
10 楼
SonicLing [专家分：6260] 发布于 2007-02-24 01:49:00
// auxiliary functions
inline bool ispair(char c1, char c2)
{
return (c1=='(' && c2==')')||c2-c1==2;
}
inline bool isleft_normal(char c)
{
return c=='(' || c=='[' || c=='{' || c=='<';
}
inline bool isprecede_normal(char c1, char c2)
{
return c1==0 || (c1=='('&&c2=='<') || ((c1!='<'||c2!='(') && c1>c2);
}
// enhanced auxiliary functions, according to bits
/*
< 3C 0011 1100 > 3E 0011 1110
( 28 0010 1000 ) 29 0010 1001
[ 5B 0101 1011 ] 5D 0101 1101
{ 7B 0111 1011 } 7D 0111 1101
*/
inline bool isleft_enhanced(char c)
{
// lowest 2 bits are the same when c is left bracket
// otherwise is right
return ((c^(c>>1))&0x01) == 0;
}
inline bool isprecede_enhanced(char c1, char c2)
{
// setting the 5th bit to the same and reversing the 3th bit, then
// all the ASCIIs of left brackets are arithmetically sorted
#define LEVEL(c) ((c|0x10)^0x04)
// or reversing both the 3th bit and the 5th bit has the same effect.
#define LEVEL2(c) (c^0x14)
return c1==0 || LEVEL2(c1)>LEVEL2(c2);
}
#define ENHANCED
#ifdef ENHANCED
#define isleft isleft_enhanced
#define isprecede isprecede_enhanced
#else
#define isleft isleft_normal
#define isprecede isprecede_normal
#endif
// test, recursive version
const char * test_r(const char *begin, char parent=0)
{
if(*begin == 0) return 0;
while(true)
{
char left = *begin;
if( left==0 || !isleft(left) ) return begin;
if( !isprecede(parent, left) ) return 0; // precedence failure
if( (begin = test_r(++begin, left))==0 || !ispair(left, *begin++) )
return 0; // precedence failure or not matched
}
return 0;
}
// test, non-recursive version
enum {stack_size=1024};
inline char * alloc_stack(size_t size)
{
static char s_stack[stack_size];
if(size <= stack_size) return s_stack;
else return new char[size];
}
inline void dealloc_stack(char *stack, size_t size)
{
if(size > stack_size) delete[] stack;
}
const char * test(const char *begin)
{
// size of the stack that needed must not be larger than 4
// because of the precedence
//size_t size = strlen(begin);
const size_t size = 16; // 16 is enough
char *stack = alloc_stack(size);
char *s_top = stack;
*(++s_top) = *begin++; // push
while(s_top != stack && *begin != 0)
{
// push left, or pop stack top for comparing
if(isleft(*begin))
{
if(isprecede(*s_top, *begin)) // precedence
*(++s_top) = *begin++; // push
else goto fail;
}
else if(!ispair(*s_top--/*pop*/, *begin++)) goto fail;
}
if(*begin != 0 || s_top != stack) goto fail;
dealloc_stack(stack, size);
return begin;
fail:
dealloc_stack(stack, size);
return 0;
}
// match
bool match(char* str)
{
// enhanced version is faster than unenhanced version
// non-recursive version is faster than recursive version
// so enhanced non-recursive version is the fastest one
const char *end = test(str);
return end != 0;
}
// match recursive version
bool matchr(char* str)
{
const char *end = test_r(str);
return end != 0;
}
我来回复
您所在位置：