算法笔记——括号匹配_括号匹配算法

算法问题

判断括号是否匹配：给定n组数，每组为一个字符串，测试3种括号：{}，[]，(),且顺序只能是先左括号，后右括号，括号间可以嵌套。若匹配成功则输出yes，否则输出no；
如：{@}a、{[()]} 都是匹配；
{[[]}、{}{ 都是不匹配。

Input：

2
{a}[b]（d）
{[(]}

Output:

yes
no

解题思路

该问题用栈来解决

1. 当第一字符是左括号时，压入栈中；是数字的时候不压入栈，就当没看到；若是右括号则直接返回false；
2. 依次遍历字符数组，当是左括号仍然压入栈；
3. 是右括号判断栈是否空，若空则右括号无法匹配，返回false；若栈不空，则判断此时栈顶的括号是否与该右括号匹配，如果匹配 ，弹出该字符，继续遍历字符数组；如果不匹配遍历结束，直接返回false；
4. 遍历一遍字符数组结束，如果都匹配则此时栈内容为空，即是s.top==-1,这时表明括号都是匹配的；如果栈不为空说明有左括号没得到匹配，匹配失败。

完整代码

#include<stdio.h>
#include<math.h>
#include<string.h>
#define MaxSize 10
//交换函数 
void swap(int &a,int &b){
	int t;
	t=a;
	a=b;
	b=t;
}
typedef struct {
	char data[MaxSize];
	int top;
}SeqStack;

//初始化栈 
void InitStack(SeqStack &s){
	s.top=-1;
}

//判断栈是否为空
bool StackEmpty(SeqStack &s){
	if(s.top==-1) return true;
	else return false;
} 

//进栈
bool push(SeqStack &s,char x){
	if(s.top==MaxSize-1) return false;
	s.top++;
	s.data[s.top]=x;
	return true;
} 

//出栈
bool pop(SeqStack &s,char &x){
	if(s.top==-1) return false;
	x=s.data[s.top];
	s.top--;
	return true;
} 

//匹配算法
bool check(char str[],int l){
	SeqStack s;
	InitStack(s);
	for(int i=0;i<l;i++){
		if(str[i]=='('||str[i]=='['||str[i]=='{'){
		push(s,str[i]);
	}
		
		else {
		if(StackEmpty(s)) return false;
		//当是右括号是判断是否匹配，把字母过滤掉 
		if(str[i]==')'||str[i]==']'||str[i]=='}'){
		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);
} 
int main(){
	int n,m;
	scanf("%d\n",&n);
	char c;
	char str[20];
	while(n--){
		int l=0;
		while((c=getchar())!='\n'){
			str[l]=c;
			l++;
		}
		
		if(check(str,l)) printf("yes\n");
		else printf("no\n");
	}
	return 0;
}
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