【3.A.S.T】网络安全爱好者 » 程序设计 » 第49次编程比赛题目

大眼娃娃 发表于 2008-9-29 09:23

第49次编程比赛题目

第49次编程比赛题目
第49次编程比赛题目2007-03-14 10:53题目：给出一个包含各种括号的表达式，判断括号是否配对。括号配对的条件：括号必须先左后右，并且左右括号数量相等；对于多重括号，从外到内嵌套顺序为：{} -> [] -> () -> <>。例如{[(<>)]}。

接口： bool match(char* str);    合法返回true， 否则返回false。

输入范例：
{[(<>)]}
{}
<(>)
<()>

返回：
true
true
false
false



~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~`

/*------------------------------------------------------------------------*/
/*    给出一个包含各种括号的表达式，判断括号是否配对。                      */
/*    括号配对的条件：括号必须先左后右，并且左右括号数量相等；              */
/*    对于多重括号，从外到内嵌套顺序为：{} -> [] -> () -> <>   例如{[(<>)]} */
/*    接口： 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)
           {
           case '<': case '(': case '[': case '{':
                if ((top < 0) || (GET_PRJ(str) < GET_PRJ(stack[top])))

                {//判断左括号是否合法
                     stack[++top] = str;
                }
                else
                {
                     free(stack);
                     return FALSE;
                }
                break;
           case '>': case ')': case ']': case '}':
                if ((top < 0)   || (str - stack[top] < 0)
                               || (str - 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;
      }[url=http://hi.baidu.com/deltree]林子的江南小居[/url]


新BLOG，欢迎大家去踩点……
[url=http://bbs.yeshack.com/javascript:;][img]http://bbs.yeshack.com/images/default/msnadd.gif[/img][/url] [url=http://bbs.yeshack.com/javascript:;][img]http://bbs.yeshack.com/images/default/msnchat.gif[/img][/url] [url=http://wpa.qq.com/msgrd?V=1&Uin=759752966&Site=Yes黑客联盟论坛&Menu=yes][/url] [url=http://edit.yahoo.com/config/send_webmesg?.target=herj001@yahoo.com.cn&.src=pg][/url]

嘉瓜 发表于 2008-9-29 09:23

呼呼,,,新手的莪,,,,哎,,

cywsh 发表于 2008-9-29 09:23

头疼... 我嘛时候才能学会自己编点东西来着.. 愁死..最好的辛苦..是想你想到哭..

查看完整版本: 第49次编程比赛题目