括号匹配
假设表达式中允许包含三种括号：圆括号( )、方括号[ ]和花括号{ }，其嵌套的顺序随意。
{ ( [ ] ( ) ) }或[ { ( [ ] [ ] ) } ]等为正确的格式，[ ( ] 、( [ ( ) ) 、( ( ) ]均为不正确的格式。
检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。
例如考虑下列括号序列：
| [ |
( |
[ |
] |
[ |
] |
) |
] |
| 1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
当计算机接受了第一个括号后，它期待着与其匹配的第八个括号的出现，然而等来的却是第二个括号，此时第一个括号‘[’只能暂时靠边，而迫切等待与第二个括号相匹配的、第七个括号‘)’的出现…这个处理的过程与栈的特点相吻合。
由此，在算法中设置一个栈，每读入一个括号，若是右括号，则使置于栈顶的最急迫的期待得以消解，若是左括号，则作为一个新的更急迫的期待压入栈中，自然使原有的在栈中的所有未消解的期待的急迫性都降了一级。另外，在算法的开始和结束时，栈都应该是空的。
BracketMatching.c利用了前面的C封装的顺序栈对象 用线性表表示的顺序栈
实现了输入任意一串字符串，检测字符串中三种括号是否匹配的功能。
github源码
BracketMatching.c文件
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
| #include <stdio.h>
#include <malloc.h>
#include "LinearListStack.h"
int bracketMatching(char *str){
char elem;
int result = 0;
int bracket_contained = 0;
LinearListStack *stack = InitLinearListStack();
while(*str != '\0'){
if(*str == '{' || *str == '[' || *str == '('){
bracket_contained = 1;
stack->push(stack,str);
}else if(*str == '}'){
bracket_contained = 1;
if(stack->length(stack)){
stack->getTop(stack,&elem);
if(elem == '{'){
stack->pop(stack,&elem);
}else if(elem == '('){
printf("Bracket matching failed : \')\' expected! \n");
DestroyLinearListStack(stack);
return 0;
}else if(elem == '['){
printf("Bracket matching failed : \']\' expected! \n");
DestroyLinearListStack(stack);
return 0;
}
}else{
printf("Bracket matching failed : \'{\' expected! \n");
DestroyLinearListStack(stack);
return 0;
}
}else if(*str == ']'){
bracket_contained = 1;
if(stack->length(stack)){
stack->getTop(stack,&elem);
if(elem == '['){
stack->pop(stack,&elem);
}else if(elem == '{'){
printf("Bracket matching failed : \'}\' expected! \n");
DestroyLinearListStack(stack);
return 0;
}else if(elem == '('){
printf("Bracket matching failed : \')\' expected! \n");
DestroyLinearListStack(stack);
return 0;
}
}else{
printf("Bracket matching failed : \'[\' expected! \n");
DestroyLinearListStack(stack);
return 0;
}
}else if(*str == ')'){
bracket_contained = 1;
if(stack->length(stack)){
stack->getTop(stack,&elem);
if(elem == '('){
stack->pop(stack,&elem);
}else if(elem == '['){
printf("Bracket matching failed : \']\' expected! \n");
DestroyLinearListStack(stack);
return 0;
}else if(elem == '{'){
printf("Bracket matching failed : \'}\' expected! \n");
DestroyLinearListStack(stack);
return 0;
}
}else{
printf("Bracket matching failed : \'(\' expected! \n");
DestroyLinearListStack(stack);
return 0;
}
}
str++;
}
if(bracket_contained){
if(stack->length(stack) == 0){
printf("Bracket matching successed\n");
result = 1;
}else{
stack->getTop(stack,&elem);
switch(elem){
case '{':
printf("Bracket matching failed : \'}\' expected! \n");
break;
case '[':
printf("Bracket matching failed : \']\' expected! \n");
break;
case '(':
printf("Bracket matching failed : \')\' expected! \n");
break;
}
result = 0;
}
}else{
printf("String doesn't contain bracket!\n");
result = 0;
}
DestroyLinearListStack(stack);
return result;
}
int main(void)
{
int num;
char str[100];
printf("please enter a string!\n");
gets(str);
printf("\n");
bracketMatching(str);
return 0;
}
|
编译：
1
| gcc LinearListStack.c LinearListStack.h BracketMatching.c -o BracketMatching
|
运行BracketMatching,显示：
示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| 输入：
DestroyLinearListStack(stack);
Bracket matching successed
输入：
if(stack->length(stack) == 0){
Bracket matching failed : '}' expected!
输入：
if(stack->length(stack))
Bracket matching successed
输入：
([())
Bracket matching failed : ']' expected!
输入：
(()]
Bracket matching failed : ')' expected!
输入：
if(elem == '(')
Bracket matching failed : ')' expected!
输入：
[([][])]
Bracket matching successed
|
