数据结构(C++版)——栈的应用，利用栈的先进后出判断一个包含“(“和“)“ “[“和“]“ “＜“和“＞“ “{“和“}“的括号序列是否匹配

客官°小女子只卖身不卖艺 2022-11-20 02:59 113阅读 0赞

## 数据结构(C++版)——栈的应用，编写程序判断一个包含"(“和”)" “\[“和”\]” “<“和”>” "\{“和”\}"的括号序列是否匹配 ##

## 1.编译运行 ##

![在这里插入图片描述][20201117205244222.gif_pic_center]

*  需求：

> 判断一个包含"(“和”)" “\[“和”\]” “<“和”>” "\{“和”\}"的括号序列是否匹配，匹配输出match；若不匹配，输出not match

*  样例:

> 1.输入： <\[\]\{\}()>  
> 输出:：match  
> 2.输入：<<  
> 输出： not match

*  分析：

> 1.利用栈的先进后出  
> 2.遇到左括号压栈  
> 3.遇到右括号，与栈顶元素比较，如果栈非空并且栈顶是同类型的左括号，则出栈，表明匹配，如果栈空，说明右括号多，不匹配

## 2.代码块 ##

*  定义栈的存储结构

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

*  顺序栈初始化

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 flag =1;
    	char e;
    	for(int i=0;i<str.length();i++){ 											
    		switch(str[i]){ 	
    			//1.左括号进栈 
    			case '(':
    			case '<':
    			case '{':									
    			case '[':{ 
    				push(S,str[i]);	
    				break;
    			}
    			// 2.右括号 
    			//与栈顶元素比较，如果栈非空并且栈顶是同类型的左括号，则出栈，表明匹配 
    			//如果栈空，说明右括号多，不匹配 
    			case '>':{ 
    				GetTop(S,e);									
    				if(	!stackEmpty(S)	&&	e=='<') 
    					pop(S,e);								
    				else 
    					flag=0;	
    				break;
    			}																	
    			case ')':{ 
    				GetTop(S,e);									
    				if(	!stackEmpty(S)	&&	e=='(') 
    					pop(S,e);								
    				else 
    					flag=0;	
    				break;
    			}
    			case '}':{ 
    				GetTop(S,e);									
    				if(	!stackEmpty(S)	&&	e=='{') 
    					pop(S,e);								
    				else 
    					flag=0;	
    				break;
    			}								
    			case ']':{ 
    				GetTop(S,e);									
    				if(	!stackEmpty(S)	&&	e=='[') 
    					pop(S,e);								
    				else 
    					flag=0;
    				break;
    			}
    			default :
    				flag=0;								
    		}										
    	}
    	//3.表达式比较结束 
    	//如果栈空，说明匹配成功，返回1 
    	//如果栈空，则栈内还有左括号，说明左括号多了，匹配不成功，返回0 
    	if(	stackEmpty(S)	&&	flag==1	) return 1;											
    	else return 0;
    }

## 3.源码 ##

#include<iostream>
    using namespace std;
    #define ERROR 0
    #define OK 1
    #define MAXSIZE 100000
    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 flag =1;
    	char e;
    	for(int i=0;i<str.length();i++){ 											
    		switch(str[i]){ 	
    			//1.左括号进栈 
    			case '(':
    			case '<':
    			case '{':									
    			case '[':{ 
    				push(S,str[i]);	
    				break;
    			}
    			// 2.右括号 
    			//与栈顶元素比较，如果栈非空并且栈顶是同类型的左括号，则出栈，表明匹配 
    			//如果栈空，说明右括号多，不匹配 
    			case '>':{ 
    				GetTop(S,e);									
    				if(	!stackEmpty(S)	&&	e=='<') 
    					pop(S,e);								
    				else 
    					flag=0;	
    				break;
    			}																	
    			case ')':{ 
    				GetTop(S,e);									
    				if(	!stackEmpty(S)	&&	e=='(') 
    					pop(S,e);								
    				else 
    					flag=0;	
    				break;
    			}
    			case '}':{ 
    				GetTop(S,e);									
    				if(	!stackEmpty(S)	&&	e=='{') 
    					pop(S,e);								
    				else 
    					flag=0;	
    				break;
    			}								
    			case ']':{ 
    				GetTop(S,e);									
    				if(	!stackEmpty(S)	&&	e=='[') 
    					pop(S,e);								
    				else 
    					flag=0;
    				break;
    			}
    			default :
    				flag=0;								
    		}										
    	}
    	//3.表达式比较结束 
    	//如果栈空，说明匹配成功，返回1 
    	//如果栈空，则栈内还有左括号，说明左括号多了，匹配不成功，返回0 
    	if(	stackEmpty(S)	&&	flag==1	) return 1;											
    	else return 0;
    } 
    
    int main(){ 
    	//创建栈S 
    	SqStack S;
    	//初始化栈S 
    	InitStack(S);
    	string str;	
    	cout<<"请输入括号组成的序列:"<<endl;
    	cin>>str;
    	cout<<"括号序列为:"<<endl;
    	cout<<str<<endl;
    	//根据match返回的1,0输出match或not match 
    	if(match(S,str)){ 
    		cout<<"match"<<endl;
    	}else
    		cout<<"not match"<<endl;												
    	return 0;
    }

[20201117205244222.gif_pic_center]: /images/20221120/08b6a1ab212a40ad9e1bf5a83a0eda5c.png