返回列表 发帖

第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;
      }林子的江南小居


新BLOG,欢迎大家去踩点……
[/url] [url=http://edit.yahoo.com/config/send_webmesg?.target=herj001@yahoo.com.cn&.src=pg]

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

TOP

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

TOP

返回列表