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

一、编译运行

需求

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

样例:

1.输入 []{}()

输出: match

2.输入

输出 not match

分析

1.利用栈的先进后出

2.遇到左括号压栈

3.遇到右括号 与栈顶元素比较 如果栈非空并且栈顶是同类型的左括号 则出栈 表明匹配 如果栈空 说明右括号多 不匹配

代码块定义栈的存储结构

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;

} 

源码

#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; 


 //与栈顶元素比较 如果栈非空并且栈顶是同类型的左括号 则出栈 表明匹配 

 //如果栈空 说明右括号多 不匹配 

 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;

【数据结构】栈的实现 栈：是一种特殊的线性表，其只允许在固定的一端进行插入与删除操作。进行数据的插入和删除的一端称为栈顶，另一端称为栈底。