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
| #include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
//万一存满了，可以用链栈
#define MaxSize 10 //定义栈中元素的最大个数
typedef struct{
char data[MaxSize]; //静态数组存放栈中元素
int top; //栈顶指针
}SqStack;
//初始化栈
void InitStack(SqStack *S){
S->top=-1; //初始化栈顶指针
}
//判断栈空
bool StackEmpty(SqStack *S){
if(S->top == -1){
return true; //栈空
}
else{
return false; //不空
}
}
//新元素入栈
bool Push(SqStack *S,char x){
if(S->top==MaxSize-1){
return false; //栈满，报错
}
S->top=S->top+1; //指针先+1
S->data[S->top]=x; //新元素入栈
return true;
}
//栈顶元素出栈，用x返回
bool Pop(SqStack *S,char *x){
if(S->top==-1){
return false; //栈空，报错
}
(*x)=S->data[S->top]; //栈顶元素先出栈
S->top=S->top-1; //指针再-1，数据还残留在内存中，只是逻辑上被删除了
return true;
}
bool bracketCheck(char str[],int length){
SqStack S;
InitStack(&S); //初始化一个栈
for(int i=0;i<length;i++){
if(str[i]=='(' || str[i]=='[' || str[i]=='{'){
Push(&S,str[i]); //扫描到左括号，入栈
}else{
if(StackEmpty(&S)){ //扫描到右括号，且当前栈空
return false; //匹配失败
}
char topElem;
Pop(&S,&topElem); //栈顶元素出栈
if(str[i]==')' && topElem != ')'){
return false;
}
if(str[i]==']' && topElem != '['){
return false;
}
if(str[i]=='}' && topElem != '{'){
return false;
}
}
}
return StackEmpty(&S); //检索完全部括号后，栈空说明匹配成功
}
|
