第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，欢迎大家去踩点……