1.编译运行
- 需求
请编写程序判断一个包含“（”和“）”的括号序列是否匹配。如匹配则输出Match；如不匹配，计算出使该序列变为匹配序列所需添加的最少括号数目（只允许在该序列开始和结尾处添加括号），并输出经添加最少括号后得到的合法匹配序列。
- 输入格式
输入为一个字符串，包含不超过100000个括号。
- 输出格式
若输入的括号序列匹配，则输出Match。若不匹配，则输出分为2行，第1行为一个整数，表示将该序列变为匹配序列所需添加的最少括号数目，第2行为一个字符串，表示经添加最少括号后得到的合法匹配序列。
2.样例
- 输入样例1:
(())()
- 输出样例1:
Match
- 输入样例2:
)(
- 输出样例2:
2
()()
- 输入样例3:
4
((()))(())
3.代码块
- 顺序栈存储结构定义
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; }
- 括号匹配
intflag=1; chare; for(inti=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或输出需要补的括号
if( stackEmpty(S) &&flag==1 ) { cout<<"Match"<<endl; //否则如果栈空，则栈内还有左括号，说明左括号多了，匹配不成功，需要补同等数量的右括号 }else{ if(!stackEmpty(S)) right=right+S.top-S.base; cout<<left+right<<endl; for(inti=0;i<left;i++) cout<<'('; cout<<str; for(inti=0;i<right;i++) cout<<')'; }
4.源码
#include<iostream>usingnamespacestd; #defineERROR0#defineOK1#defineMAXSIZE100001typedefcharSElemType; 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,int&count){ } intmain(){ //创建栈S SqStackS; //记录需要补的左括号 intleft=0; //记录需要补的右括号 intright=0; //初始化栈S InitStack(S); stringstr; cin>>str; //根据match返回的1,0输出match或not matchintflag=1; chare; for(inti=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(inti=0;i<left;i++) cout<<'('; cout<<str; for(inti=0;i<right;i++) cout<<')'; } return0; }
