栈的数组实现和括号匹配的检查

@Author: 张海拔

@Update: 2014-01-17

@Link: http://www.cnblogs.com/zhanghaiba/p/3516795.html

 

栈的数组实现示例(不封装,直接使用)

 1 /*
 2  *Author: ZhangHaiba
 3  *Date: 2014-1-12
 4  *File: stack_array_private.c
 5  *
 6  *a demo shows stack base on array implementation without package
 7  */
 8 
 9 #include <stdio.h>
10 #define ST_LEN 1024 //the depth of stack
11 #define STR_LEN 256
12 
13 int check(char *);
14 
15 //public form main.c
16 int stack[ST_LEN];
17 int sp = 0; //point to next empty space
18 
19 int main(void)
20 {
21     char str[STR_LEN];
22     int testcase;
23 
24     scanf("%d", &testcase);
25     while (testcase--) {
26         scanf("%s", str);
27         printf(check(str) ? "ok\n" : "error\n");
28     }
29     return 0;
30 }
31 
32 int check(char *s)
33 {
34     int i;
35             
36     sp = 0; //stack clear
37     for (i = 0; s[i]; ++i) {
38         switch(s[i]) {
39         case '(':
40             stack[sp++] = s[i]; //stack push
41             break;
42         case '[':
43             stack[sp++] = s[i];
44             break;
45         case '{':
46             stack[sp++] = s[i];
47             break;
48         case ')':
49             if (sp > 0 && stack[sp-1] ==  '(') //stack is not empty && stack top == '('
50                 --sp; //stack pop;
51             else
52                 return 0;
53             break;
54         case ']':
55             if (sp > 0 && stack[sp-1] == '[')
56                 --sp;
57             else
58                 return 0;
59             break;
60         case '}':
61             if (sp > 0 && stack[sp-1] == '{')
62                 --sp;
63             else
64                 return 0;
65             break;
66         default:
67             break;
68         }
69     }
70     return sp <= 0;
71 }

 

栈的数组实现示例(带封装)

  1 /*
  2  *Author: ZhangHaiba
  3  *Date: 2014-1-12
  4  *File: stack_array_private.c
  5  *
  6  *a demo shows stack base on array implementation with package by module method
  7  */
  8 
  9 #include <stdio.h>
 10 #define ST_LEN 1024 //the depth of stack
 11 #define STR_LEN 256
 12 
 13 //public from stack.h
 14 void push(int);
 15 int pop();
 16 int top();
 17 int is_empty();
 18 int is_full();
 19 void clear();
 20 
 21 //private form stack.c
 22 //you can use "static" to get internel linkage
 23 int stack[ST_LEN];
 24 int sp = 0; //point to next empty space
 25 
 26 //public form main.h
 27 int check(char *);
 28 
 29 int main(void)
 30 {
 31     char str[STR_LEN];
 32     int testcase;
 33 
 34     scanf("%d", &testcase);
 35     while (testcase--) {
 36         scanf("%s", str);
 37         printf(check(str) ? "ok\n" : "error\n");
 38     }
 39     return 0;
 40 }
 41 
 42 int check(char *s)
 43 {
 44     int i;
 45             
 46     clear();
 47     for (i = 0; s[i]; ++i) {
 48         switch(s[i]) {
 49         case '(':
 50             push(s[i]);
 51             break;
 52         case '[':
 53             push(s[i]);
 54             break;
 55         case '{':
 56             push(s[i]);
 57             break;
 58         case ')':
 59             if (!is_empty() && top() == '(')
 60                 pop();
 61             else
 62                 return 0;
 63             break;
 64         case ']':
 65             if (!is_empty() && top() == '[')
 66                 pop();
 67             else
 68                 return 0;
 69             break;
 70         case '}':
 71             if (!is_empty() && top() == '{')
 72                 pop();
 73             else
 74                 return 0;
 75             break;
 76         default:
 77             break;
 78         }
 79     }
 80     return is_empty();
 81 }
 82 
 83 void push(int item)
 84 {
 85     if (!is_full())
 86         stack[sp++] = item;
 87 }
 88 
 89 int pop()
 90 {
 91     if (!is_empty())
 92         return stack[--sp];
 93 }
 94 
 95 int top()
 96 {
 97     if (!is_empty())
 98         return stack[sp-1];
 99 }
100 
101 int is_full()
102 {
103     return sp >= ST_LEN;
104 }
105 
106 int is_empty()
107 {
108     return sp <= 0;
109 }
110 
111 int size()
112 {
113     return sp;
114 }
115 
116 void clear()
117 {
118     sp = 0;
119 }

 

因为单纯用数组来实现栈显得很单调,所以引入了括号匹配的检查问题:

检查一段不包括空白字符的字符串中,括号匹配是否合法(即看是不是一个支持 ()[]{} 括号的广义表形式)

 

测试用例

输入:
8
(a+b)[4*5+(-6)]
(a+b)[4*5+(-6)])
())
(
(()
(fadfs[fds](fd[fd]d(x)))
)))(((
)(

输出:
ok
error
error
error
error
ok
error
error

 

其实,使用栈数据结构时,我经常用 C++ STL 的 <stack>,因为它是动态分配的不需要考虑栈的深度,也因为被封装得足够好。

在 C 语言中,也可以用链栈(链表实现的栈)加上封装来达到上面的效果。

在可以预见栈最大深度时,常常用数组来实现栈——

OJ 刷题经常用裸的栈(就是一个数组,仅仅假象它受限:FILO),实现如 demo1 中所示,这样一来封装性和可读性都很差,不过 OJ 解题都是快速写成的小程序,这样做无可厚非。

工程中必须考虑数据的保护,防止意外修改和降低耦合,所以会用单独的模块来实现 stack,实现如 demo2 所示,当然上面的写法只是一种思想封装(真的封装要靠多文件和 static)。

 

小结:栈的实现关键在于 sp 游标(或说指针)的操作,sp(stack pointer) 一般设置为指向下一个空闲空间的位置。

发表评论

电子邮件地址不会被公开。 必填项已用*标注