数据结构PTA72——括号匹配

发表于

这是我参与11月更文挑战的第18天，活动详情查看：2021最后一次更文挑战

1.编译运行

在这里插入图片描述

  • 需求

请编写程序判断一个包含“（”和“）”的括号序列是否匹配。如匹配则输出Match；如不匹配，计算出使该序列变为匹配序列所需添加的最少括号数目（只允许在该序列开始和结尾处添加括号），并输出经添加最少括号后得到的合法匹配序列。

  • 输入格式

输入为一个字符串，包含不超过100000个括号。

  • 输出格式

若输入的括号序列匹配，则输出Match。若不匹配，则输出分为2行，第1行为一个整数，表示将该序列变为匹配序列所需添加的最少括号数目，第2行为一个字符串，表示经添加最少括号后得到的合法匹配序列。

2.样例

  • 输入样例1:

(())()

  • 输出样例1:

Match

  • 输入样例2:

)(

  • 输出样例2:

2

()()

  • 输入样例3:

4

((()))(())

3.代码块

  • 顺序栈存储结构定义
1
2
3
4
5
6
7
8
cpp复制代码typedef struct{
	//top指针指向栈顶 
	SElemType *top;
	//base指针指向栈底 
	SElemType *base;
	//顺序栈的大小 
	int stackSize;
}SqStack;
  • 顺序栈S初始化
1
2
3
4
5
6
7
8
9
10
11
12
cpp复制代码Status InitStack(SqStack &S){
	//动态分配一个SElemType类型MAXSIZE长度的空间
	//将地址给顺序栈S的栈底指针 
	S.base = new SElemType[MAXSIZE];
	//判断，若顺序栈的栈底指针(S.base)为空，没有地址，则没有分配成功 
	if(!S.base) return ERROR;
	//空的顺序栈，所以栈顶指针=栈底指针 
	S.top=S.base;
	// 空的顺序栈，由MAXSIZE个空间可以存 
	S.stackSize = MAXSIZE;
	return OK;
}
  • 进栈,将e压入顺序栈S中
1
2
3
4
5
6
7
cpp复制代码Status push(SqStack &S,SElemType e){
	//判断栈是否满栈 
	if(S.top-S.base==S.stackSize) return ERROR;
	//将e存入S.top，存入栈顶，栈顶指针top++向上移动 
	*S.top++=e;
	return OK;
}
  • 出栈，将栈顶元素给e
1
2
3
4
5
6
7
cpp复制代码Status pop(SqStack &S,SElemType &e){
	//判断栈内是否有元素,为空栈 
	if(S.top==S.base) return ERROR;
	//栈顶指针下移，将栈顶元素赋给e 
	e=*--S.top;
	return OK; 
}
  • 取栈顶元素 ,赋值给e
1
2
3
4
5
6
7
cpp复制代码Status GetTop(SqStack S,SElemType &e){
	//判断栈内是否有元素,为空栈 
	if(S.top==S.base) return ERROR; 
	//返回栈顶元素的值，栈顶指针不变 
	e=*(S.top-1); 
	return OK; 
}
  • 判断栈是否为空
1
2
3
4
5
6
7
cpp复制代码int stackEmpty(SqStack S){
	//空返回1 
	if(S.top==S.base) 
		return 1;
	//非空返回0 
	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
cpp复制代码	int flag =1; 
	char e;
	for(int i=0;i<str.length();i++){											
		switch(str[i]){	
			//1.左括号进栈											
			case '(':
				push(S,str[i]);	
				break;
			// 2.右括号																																				
			case ')':
				{
					//与栈顶元素比较，如果栈非空并且栈顶是同类型的左括号，则出栈，表明匹配	
					GetTop(S,e);									
					if(	!stackEmpty(S)	&&	e=='(') 
						pop(S,e);
					//如果栈空,说明右括号多,不匹配,需要补左括号									
					else{
						left++;
						flag=0;
						} 
				}	
				break;
		}						
	}
  • 输出Match或输出需要补的括号
1
2
3
4
5
6
7
8
9
10
11
12
13
cpp复制代码if(	stackEmpty(S)	&&	flag==1	) {
		cout<<"Match"<<endl;
	//否则如果栈空，则栈内还有左括号，说明左括号多了，匹配不成功，需要补同等数量的右括号	
	}else{
		if(!stackEmpty(S))
			right =right+S.top-S.base;		
		cout<<left+right<<endl;	
		for(int i=0;i<left;i++)
			cout<<'(';
		cout<<str;
		for(int i=0;i<right;i++)
			cout<<')';
	}

4.源码

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
114
115
116
117
118
119
120
121
122
123
124
125
126
cpp复制代码#include<iostream>
using namespace std;
#define ERROR 0
#define OK 1
#define MAXSIZE 100001
typedef char SElemType;
typedef int Status;

typedef struct{
	//top指针指向栈顶 
	SElemType *top;
	//base指针指向栈底 
	SElemType *base;
	//顺序栈的大小 
	int stackSize;
}SqStack;

//顺序栈S初始化
Status InitStack(SqStack &S){
	//动态分配一个SElemType类型MAXSIZE长度的空间
	//将地址给顺序栈S的栈底指针 
	S.base = new SElemType[MAXSIZE];
	//判断，若顺序栈的栈底指针(S.base)为空，没有地址，则没有分配成功 
	if(!S.base) return ERROR;
	//空的顺序栈，所以栈顶指针=栈底指针 
	S.top=S.base;
	// 空的顺序栈，由MAXSIZE个空间可以存 
	S.stackSize = MAXSIZE;
	return OK;
}

//进栈,将e压入顺序栈S中 
Status push(SqStack &S,SElemType e){
	//判断栈是否满栈 
	if(S.top-S.base==S.stackSize) return ERROR;
	//将e存入S.top，存入栈顶，栈顶指针top++向上移动 
	*S.top++=e;
	return OK;
}

//出栈，将栈顶元素给e 
Status pop(SqStack &S,SElemType &e){
	//判断栈内是否有元素,为空栈 
	if(S.top==S.base) return ERROR;
	//栈顶指针下移，将栈顶元素赋给e 
	e=*--S.top;
	return OK; 
} 

//取栈顶元素 ,赋值给e 
Status GetTop(SqStack S,SElemType &e){
	//判断栈内是否有元素,为空栈 
	if(S.top==S.base) return ERROR; 
	//返回栈顶元素的值，栈顶指针不变 
	e=*(S.top-1); 
	return OK; 
} 

//判断栈是否为空 
int stackEmpty(SqStack S){
	//空返回1 
	if(S.top==S.base) 
		return 1;
	//非空返回0 
	return 0; 	
} 

//利用栈先进后出消去一组的括号 
int match(SqStack &S,string str,int &count){
	
} 

int main(){
	//创建栈S 
	SqStack S;
	//记录需要补的左括号 
	int left=0;
	//记录需要补的右括号 
	int right=0;
	//初始化栈S 
	InitStack(S);
	string str;	
	cin>>str;
	//根据match返回的1,0输出match或not match
	int flag =1; 
	char e;
	for(int i=0;i<str.length();i++){											
		switch(str[i]){	
			//1.左括号进栈											
			case '(':
				push(S,str[i]);	
				break;
			// 2.右括号																																				
			case ')':
				{
					//与栈顶元素比较，如果栈非空并且栈顶是同类型的左括号，则出栈，表明匹配	
					GetTop(S,e);									
					if(	!stackEmpty(S)	&&	e=='(') 
						pop(S,e);
					//如果栈空,说明右括号多,不匹配,需要补左括号									
					else{
						left++;
						flag=0;
						} 
				}	
				break;
			}						
		}																						
	//如果栈空，且flag==1说明匹配成功，输出Match																														
	if(	stackEmpty(S)	&&	flag==1	) {
		cout<<"Match"<<endl;
	//否则如果栈空，则栈内还有左括号，说明左括号多了，匹配不成功，需要补同等数量的右括号	
	}else{
		//栈不为空，则栈里所有的括号都是'('
		if(!stackEmpty(S))
			right =right+S.top-S.base;	
		//输出需要补括号的数量	
		cout<<left+right<<endl;	
		for(int i=0;i<left;i++)
			cout<<'(';
		cout<<str;
		for(int i=0;i<right;i++)
			cout<<')';
	}														
	return 0;
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%