Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3711935
  • 博文数量: 356
  • 博客积分: 10458
  • 博客等级: 上将
  • 技术积分: 4734
  • 用 户 组: 普通用户
  • 注册时间: 2008-03-24 14:59
文章分类

全部博文(356)

文章存档

2020年(17)

2019年(9)

2018年(26)

2017年(5)

2016年(11)

2015年(20)

2014年(2)

2013年(17)

2012年(15)

2011年(4)

2010年(7)

2009年(14)

2008年(209)

分类: C/C++

2013-04-26 14:14:52

描述 现在,有一行括号序列,请你检查这行括号是否配对。
输入 第一行输入一个数N(03 [(]) (]) ([[]()]) 样例输出
No
No
Yes
题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=2

这题用栈来实现非常方便,遍历一次数据,左半边入栈,如果是右半边就与栈顶数据匹配,如果匹配则出栈,否则返回No,如果能够全部遍历完且栈为空则Yes

  1. #include   
  2. #include   
  3. #include   
  4.   
  5. static char pairs[2][2] = {{'['']'}, {'('')'}};  
  6.   
  7. struct stack  
  8. {  
  9.     char data[10000];  
  10.     int top;  
  11. };  
  12.   
  13. void init_stack(struct stack *s)  
  14. {  
  15.     s->top = -1;  
  16. }  
  17.   
  18. void push_stack(struct stack *s, char value)  
  19. {  
  20.     s->data[++s->top] = value;  
  21. }  
  22.   
  23. void pop_stack(struct stack *s)  
  24. {  
  25.     --(s->top);  
  26. }  
  27.   
  28. int is_empty(struct stack *s)  
  29. {  
  30.     return (s->top == -1);  
  31. }  
  32.   
  33. char stack_top(struct stack *s)  
  34. {  
  35.     return s->data[s->top];  
  36. }  
  37.   
  38. int is_first_pair(char a)  
  39. {  
  40.     int i;  
  41.     int n = sizeof(pairs) / sizeof(pairs[0]);  
  42.     for ( i = 0; i < n; i++ ) {  
  43.         if ( pairs[i][0] == a ) {  
  44.             return 1;  
  45.         }  
  46.     }  
  47.   
  48.     return 0;  
  49. }  
  50.   
  51. int is_pair(char a, char b)  
  52. {  
  53.     int i;  
  54.     int n = sizeof(pairs) / sizeof(pairs[0]);  
  55.     for ( i = 0; i < n; i++ ) {  
  56.         if (pairs[i][0] == a) {  
  57.             if (pairs[i][1] == b) {  
  58.                 return 1;  
  59.             } else {  
  60.                 return 0;   
  61.             }  
  62.         }  
  63.     }  
  64.   
  65.     return 0;  
  66. }  
  67.   
  68. int check_pair(char *buf, int n, struct stack *s)  
  69. {  
  70.     int i;  
  71.   
  72.     if (n <= 0)  
  73.         return 0;  
  74.   
  75.     for ( i = 0; i < n; i++ ) {  
  76.         if (is_first_pair(buf[i]))  
  77.             push_stack(s, buf[i]);  
  78.         else if ( !is_empty(s) && is_pair(stack_top(s), buf[i]) )   
  79.             pop_stack(s);  
  80.         else  
  81.             return 0;  
  82.     }  
  83.   
  84.     if (is_empty(s))  
  85.         return 1;  
  86.     else   
  87.         return 0;  
  88. }  
  89.   
  90.     int  
  91. main( int argc, char **argv )  
  92. {  
  93.     int n;  
  94.     char buf[10000];  
  95.     struct stack s;  
  96.     int i;  
  97.   
  98.     scanf("%d", &n);  
  99.     for ( i = 0; i < n; i++ ) {  
  100.         init_stack(&s);  
  101.         buf[0] = '\0';  
  102.         scanf("%s", buf);   
  103.         if (check_pair(buf, strlen(buf), &s))  
  104.             printf("Yes\n");  
  105.         else  
  106.             printf("No\n");  
  107.     }  
  108.   
  109.     return 0;  
  110. }  
作者:帅得不敢出门  c++哈哈堂31843264
阅读(1036) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~