一、编译运行
- 需求：
判断一个包含"(“和”)" “[“和”]” “<“和”>” "{“和”}"的括号序列是否匹配，匹配输出match；若不匹配，输出not match
- 样例:
1.输入： <[]{}()>
输出:：match
2.输入：<<
输出： not match
- 分析：
1.利用栈的先进后出
2.遇到左括号压栈
3.遇到右括号，与栈顶元素比较，如果栈非空并且栈顶是同类型的左括号，则出栈，表明匹配，如果栈空，说明右括号多，不匹配
代码块
- 定义栈的存储结构
typedefstruct{ //top指针指向栈顶 SElemType*top; //base指针指向栈底 SElemType*base; //顺序栈的大小 intstackSize; }SqStack;
- 顺序栈初始化
StatusInitStack(SqStack&S){ //动态分配一个SElemType类型MAXSIZE长度的空间//将地址给顺序栈S的栈底指针 S.base=newSElemType[MAXSIZE]; //判断，若顺序栈的栈底指针(S.base)为空，没有地址，则没有分配成功 if(!S.base) returnERROR; //空的顺序栈，所以栈顶指针=栈底指针 S.top=S.base; // 空的顺序栈，由MAXSIZE个空间可以存 S.stackSize=MAXSIZE; returnOK; }
- 进栈，将e压入顺序栈S中
Statuspush(SqStack&S,SElemTypee){ //判断栈是否满栈 if(S.top-S.base==S.stackSize) returnERROR; //将e存入S.top，存入栈顶，栈顶指针top++向上移动 *S.top++=e; returnOK; }
- 出栈，将栈顶元素给e
Statuspop(SqStack&S,SElemType&e){ //判断栈内是否有元素,为空栈 if(S.top==S.base) returnERROR; //栈顶指针下移，将栈顶元素赋给e e=*--S.top; returnOK; }
- 取栈顶元素 ,赋值给e
StatusGetTop(SqStackS,SElemType&e){ //判断栈内是否有元素,为空栈 if(S.top==S.base) returnERROR; //返回栈顶元素的值，栈顶指针不变 e=*(S.top-1); returnOK; }
- 判断栈是否为空
intstackEmpty(SqStackS){ //空返回1 if(S.top==S.base) return1; //非空返回0 return0; }
- 进行括号匹配
intmatch(SqStack&S,stringstr){ intflag=1; chare; for(inti=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); elseflag=0; break; } case')':{ GetTop(S,e); if( !stackEmpty(S) &&e=='(') pop(S,e); elseflag=0; break; } case'}':{ GetTop(S,e); if( !stackEmpty(S) &&e=='{') pop(S,e); elseflag=0; break; } case']':{ GetTop(S,e); if( !stackEmpty(S) &&e=='[') pop(S,e); elseflag=0; break; } default : flag=0; } } //3.表达式比较结束 //如果栈空，说明匹配成功，返回1 //如果栈空，则栈内还有左括号，说明左括号多了，匹配不成功，返回0 if( stackEmpty(S) &&flag==1 ) return1; elsereturn0; }
源码
#include<iostream>usingnamespacestd; #defineERROR0#defineOK1#defineMAXSIZE100000typedefcharSElemType; typedefintStatus; typedefstruct{ //top指针指向栈顶 SElemType*top; //base指针指向栈底 SElemType*base; //顺序栈的大小 intstackSize; }SqStack; //顺序栈S初始化StatusInitStack(SqStack&S){ //动态分配一个SElemType类型MAXSIZE长度的空间//将地址给顺序栈S的栈底指针 S.base=newSElemType[MAXSIZE]; //判断，若顺序栈的栈底指针(S.base)为空，没有地址，则没有分配成功 if(!S.base) returnERROR; //空的顺序栈，所以栈顶指针=栈底指针 S.top=S.base; // 空的顺序栈，由MAXSIZE个空间可以存 S.stackSize=MAXSIZE; returnOK; } //进栈,将e压入顺序栈S中 Statuspush(SqStack&S,SElemTypee){ //判断栈是否满栈 if(S.top-S.base==S.stackSize) returnERROR; //将e存入S.top，存入栈顶，栈顶指针top++向上移动 *S.top++=e; returnOK; } //出栈，将栈顶元素给e Statuspop(SqStack&S,SElemType&e){ //判断栈内是否有元素,为空栈 if(S.top==S.base) returnERROR; //栈顶指针下移，将栈顶元素赋给e e=*--S.top; returnOK; } //取栈顶元素 ,赋值给e StatusGetTop(SqStackS,SElemType&e){ //判断栈内是否有元素,为空栈 if(S.top==S.base) returnERROR; //返回栈顶元素的值，栈顶指针不变 e=*(S.top-1); returnOK; } //判断栈是否为空 intstackEmpty(SqStackS){ //空返回1 if(S.top==S.base) return1; //非空返回0 return0; } //利用栈先进后出消去一组的括号 intmatch(SqStack&S,stringstr){ intflag=1; chare; for(inti=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); elseflag=0; break; } case')':{ GetTop(S,e); if( !stackEmpty(S) &&e=='(') pop(S,e); elseflag=0; break; } case'}':{ GetTop(S,e); if( !stackEmpty(S) &&e=='{') pop(S,e); elseflag=0; break; } case']':{ GetTop(S,e); if( !stackEmpty(S) &&e=='[') pop(S,e); elseflag=0; break; } default : flag=0; } } //3.表达式比较结束 //如果栈空，说明匹配成功，返回1 //如果栈空，则栈内还有左括号，说明左括号多了，匹配不成功，返回0 if( stackEmpty(S) &&flag==1 ) return1; elsereturn0; } intmain(){ //创建栈S SqStackS; //初始化栈S InitStack(S); stringstr; cout<<"请输入括号组成的序列:"<<endl; cin>>str; cout<<"括号序列为:"<<endl; cout<<str<<endl; //根据match返回的1,0输出match或not match if(match(S,str)){ cout<<"match"<<endl; }elsecout<<"not match"<<endl; return0; }
