1.内容和要求
内容：编写程序，使用堆栈实现括号匹配求解。
要求：
1 ) 用户从屏幕输入连续的括号（大中小括号都有），读入括号；
2 ) 编程使用堆栈实现括号是否匹配判断。
2.解决方案
本程序可设置“期待的急迫程度”来说明括号匹配的消除顺序。左括号期待与之匹配的右括号的出现，期待的急迫程度取决于出现的时间先后顺序，后出现的则为最急迫的，这符合栈的“LIFO”特性。故在算法中设置一个栈，每读入一个括号，若是右括号，则或者使置于栈顶的最急迫的期待得以消解，或者是不合法的情况；若是左括号，则作为一个新的更为急迫的期待压入栈中，自然使原有的在栈中的所有未消解的急迫性降低一级。
需要注意的是，在算法开始和结束时，栈都应该是空的。
//检验匹配函数
void BrackCheck(){
//从终端接受连续的括号，使用字符栈S实现括号是否匹配判断
SqStack S;
InitStack(S); //初始化栈S
SElemType ch[100];
cout<<"请输入带括号如()、[]、{}的字符串: "<<endl;
cin.getline(ch,101,'\n');
SElemType *p,q;
p = ch;
while(*p != '\0'){
switch(*p){
case '(':
case '[':
case '{':
Push(S,*p++); //当为左括号时,字符串进栈同时指针p指向下一个字符
break;
case ')':
case ']':
case '}':
if(!StackEmpty(S)){ //栈非空
Pop(S,q); //当为右括号时,字符串出栈,返回字符q
if(!(q=='('&& *p==')' || q=='['&& *p==']' || q=='{'&& *p=='}')){
cout<<"右括号不匹配"<<endl;
return;
}
}
else{ //栈空
cout<<"缺少左括号"<<endl;
return;
}
default:
p++;
break;
}//switch
}//while
if(StackEmpty(S)){ //栈空
cout<<"括号完全匹配"<<endl;
}
else{ //栈非空
cout<<"缺少右括号"<<endl;
}
DestroyStack(S); //销毁栈S
}//Brackcheck
3.总结与改进
3.1总结
本程序利用栈结构具有后进先出的特性对括号进行匹配，关键在于括号何时压栈和出栈。故在除了对栈结构基本操作如栈的初始化、判断栈的空与否、压栈与出栈的操作的具体实现，还涉及对缓冲区字符串的字符进出栈的操作问题。只有左括号才进栈，其他字符均可能对左括号出栈构成影响，故使用switch语句加以分类。同时需要注意的是程序前后的空需要为空，即考虑右括号不匹配的情况。
3.2改进
在编写测试函数的过程中，在switch语句里面使用exit(ERROR)来作为不能匹配时退出的语句，但是由于main函数里面使用到do … while()语句，以达到循环测试的效果，可exit(ERROR)语句会导致整个进程或者是整个程序结束。改用return语句后，即可实现结束子函数的进程返回主调函数即main函数。如果不考虑循环测试的情况，eixt(ERROR)与return对于本程序的逻辑均为正确。
同时在main函数中使用getchar()来清除缓冲区的换行符，以保证程序重新进入BrackCheck()的cin.getline，从而保证程序的实用性和鲁棒性。
注：return 是语言级别的，它表示了调用堆栈的返回，用于结束一个函数的执行；而 exit 是系统调用级别的，它表示了一个进程的结束，即退出应用程序.
具体参见链接：
https://blog.csdn.net/qq_29350001/article/details/53096908
4.附录
#include<iostream>
using namespace std;
//预定义变量和类型
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100
#define STACKINCREMENT 10
//函数结果状态代码
typedef int Status; //返回值类型
typedef char SElemType; //栈的元素类型
typedef struct{
//顺序栈的表示
SElemType *base; //栈构造之前和销毁之后，base的值为NULL
SElemType *top; //栈顶指针
int stacksize; //当前已分配的存储空间，以元素为单位
}SqStack;
Status InitStack(SqStack &S) {
//构造一个空栈S
S.base = new SElemType[MAXSIZE];
// S.base = (SElemType*)malloc(MAXSIZE*sizeof(SElemType));
if(!S.base) exit(OVERFLOW);
S.top = S.base;
S.stacksize = MAXSIZE;
return OK;
}//InitStack
Status DestroyStack(SqStack &S){
//销毁栈S
delete S.base;
S.base = NULL;
S.top = NULL;
return OK;
}//DestroyStack
Status StackLength(SqStack S){
//返回栈的长度，即元素个数
return S.top-S.base;
}//StackLength
Status GetTop(SqStack S,SElemType &e){
//若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR
if(S.top == S.base) return ERROR;
e = *(S.top-1);
return OK;
}//GetTop
Status Push(SqStack &S,SElemType e){
//插入元素e为新的栈顶元素
if(S.top-S.base >= S.stacksize){
S.base = (SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S.base) exit(OVERFLOW); //存储分配失败
S.top = S.base+S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e;
return OK;
}//Push
Status Pop(SqStack &S,SElemType &e){
//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；
//否则返回ERROR
if(S.top == S.base) return ERROR;
e = *--S.top;
return OK;
}//Pop
Status StackEmpty(SqStack S){
//若栈S为空栈，则返回TRUE；否则返回FALSE
if(S.top == S.base) return TRUE;
return FALSE;
}//StackEmpty
void BrackCheck(){
//从终端接受连续的括号，使用字符栈S实现括号是否匹配判断
SqStack S;
InitStack(S); //初始化栈S
SElemType ch[100];
cout<<"请输入带括号如()、[]、{}的字符串: "<<endl;
cin.getline(ch,101,'\n');
SElemType *p,q;
p = ch;
while(*p != '\0'){
switch(*p){
case '(':
case '[':
case '{':
Push(S,*p++); //当为左括号时,字符串进栈同时指针p指向下一个字符
break;
case ')':
case ']':
case '}':
if(!StackEmpty(S)){ //栈非空
Pop(S,q); //当为右括号时,字符串出栈,返回字符q
if(!(q=='('&& *p==')' || q=='['&& *p==']' || q=='{'&& *p=='}')){
cout<<"右括号不匹配"<<endl;
return;
}
}
else{ //栈空
cout<<"缺少左括号"<<endl;
return;
}
default:
p++;
break;
}//switch
}//while
if(StackEmpty(S)){ //栈空
cout<<"括号完全匹配"<<endl;
}
else{ //栈非空
cout<<"缺少右括号"<<endl;
}
DestroyStack(S); //销毁栈S
}//Brackcheck
int main(){
int choice;
cout<<"—————— 括号 匹配 ——————"<<endl;
do{
BrackCheck();
cout<<"—————— 输入1继续 ——————"<<endl;
cout<<"—————— 输入0结束 ——————"<<endl;
cin>>choice;
getchar(); //清除缓冲区中残留的'\n'
}while(choice == 1);
return 0;
}//main