数据结构与算法----1.14 括号检验匹配问题

[c++]代码库

//***********************************
//功能：括号检验匹配问题
//日期：2017年10月10日
//作者：Ryan2019
//***********************************
#include <iostream>
using namespace std;
typedef char SElemType;
const int StackInitSize=10;
const int StackInc=5;
struct SStack
{
    SElemType *base,*top;
	int stacksize;
};
bool StackInit (SStack &S);//构造栈
bool Push(SStack &S,SElemType &e);//入栈
bool Pop(SStack &S,SElemType &e);//出栈
bool StackEmpty(SStack &S);//空栈
bool Match(SElemType *a);//括号检验匹配
int main()
{
	SElemType a[]="()(";
	SElemType b[]="())";
	SElemType c[]="()()";
	cout<<"表达式a为："<<a<<endl;	
	if(Match(a))
	{	cout<<"表达式中的括号匹配！"<<endl;	}
	else
	{	cout<<"表达式中的括号不匹配！"<<endl;}
	cout<<"表达式b为："<<b<<endl;
	if(Match(b))
	{	cout<<"表达式中的括号匹配！"<<endl;	}
	else
	{	cout<<"表达式中的括号不匹配！"<<endl;}
	cout<<"表达式c为："<<c<<endl;
	if(Match(c))
	{	cout<<"表达式中的括号匹配！"<<endl;	}
	else
	{	cout<<"表达式中的括号不匹配！"<<endl;}
	return 0;
}
bool StackInit (SStack &S)
{
	S.base=new SElemType[StackInitSize];
	if(!S.base) return false;
	S.top=S.base;
	S.stacksize=StackInc;
	return true;
}
bool StackEmpty(SStack &S)
{
	return S.top==S.base;
}
bool Push(SStack &S,SElemType &e)
{
	SElemType *base;
	if(S.top-S.base==S.stacksize)
	{
		base=(SElemType*)realloc(S.base,(S.stacksize+StackInc)*sizeof(SElemType));
		if(!base) return false;
		S.base=base;
		S.top=S.base+S.stacksize;
		S.stacksize+=StackInc;
	}
	*S.top=e;
	S.top++;
	return true;
}
bool Pop(SStack &S,SElemType &e)
{
	if(S.top==S.base) return false;
	S.top--;
	e=*S.top;
	return true;
}
bool Match(SElemType *a)
{	
	SStack S;
	StackInit(S);
	SElemType e;	
	int i=0;
	while(a[i]!='\0')
	{		
		if(a[i]=='(' ||a[i]=='[' || a[i]=='{' )
		{			
			Push(S,a[i]);
		}
		else if(a[i]==')' ||a[i]==']' || a[i]=='}')
		{
			if(!Pop(S,e))
			{
				return false;
			}
			if(e=='(' && a[i]==')' || e=='[' && a[i]==']'|| e=='{' && a[i]=='}')
			{
				i++;	
				continue;
			}
			else{		
				return false;
			}
		}
		else{		
			i++;
			continue;
		}
        i++;
	}
	return StackEmpty(S);
}