#include <iostream>
#include<assert.h>
#include<cstring>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
const int stackIncreament=20; //栈溢出时扩展空间的增量
const int maxLength=100; //最大字符串长度
template<class T>
class SeqStack
{
private:
T*elements; //存放栈中元素的栈数组
int top; //栈顶指针
int maxSize; //栈最大可容纳元素
public:
SeqStack(int sz); //建立一个空栈
~SeqStack(){delete[]elements;} //析构函数
void overflowProcess();
void Push(T& x);
//如果Isfull(),则溢出处理；否则把x插入到栈顶
bool Pop(T& x);
bool IsEmpty(){return(top==-1)?true:false;}
bool IsFull(){return(top==maxSize-1)?true:false;}
int getSize()const{return top+1;}
void PrintMatchPairs(char *expression);
friend ostream& operator<<(ostream& os,SeqStack<T>& s)
{
os<<"top="<<s.top<<endl;
for(int i=0;i<s.top;i++)
{
os<<i<<":"<<s.elements[i]<<endl;
}
return os;
}
};
template<class T>
SeqStack<T>::SeqStack(int sz)
//建立一个最大尺寸为sz的空栈，若分配不成功则错误处理
{
top=-1;
maxSize=sz;
elements=new T[maxSize];
assert(elements!=NULL);//断言：动态存储分配成功与否
}
template <class T>
void SeqStack<T>::overflowProcess()
//扩充栈的存储空间
{
T*newArray=new T[maxSize+stackIncreament];
if(newArray==NULL)
{
cout<<"存储分配失败！"<<endl;
exit(1);
}
for(int i=0;i<top;i++)
{
newArray[i]=elements;
}
maxSize=maxSize+stackIncreament;
delete[]elements;
elements=newArray;
}
template <class T>
void SeqStack<T>::Push(T& x)
{
if(IsFull()==true)
overflowProcess(); //栈满则溢出处理
elements[++top]=x; //栈顶指针先+1，再进栈
}
template <class T>
bool SeqStack<T>::Pop(T& x)
{
if(IsEmpty()==true)
return false;
x=elements[top--]; //栈顶指针退1
return true; //退栈成功
}
template <class T>
void PrintMatchPairs(char *expression)
//从左向右扫描左括号入栈，当扫描到第一个右括号时，将它与栈顶的左括号匹配，匹配成功删除该左括号
{
SeqStack<int>s1(maxLength); //栈s存储 ，建立一个空栈，以方便存储（）括号
SeqStack<int>s2(maxLength); //存[]括号
SeqStack<int>s3(maxLength); //存{}括号
int j;
int length=strlen(expression); //字符串的长度
for(int i=1;i<length;i++) //在表达式中搜索"("和")"
{
j=i-1;
if(expression[i-1]=='(') //左圆括号，位置进栈
s1.Push(i);
else if (expression[i-1]==')') //右圆括号
{
if(s1.Pop(j)==true) //栈不空，退栈成功
cout<<j<<"与"<<i<<"匹配"<<endl;
else
cout<<"没有与第"<<i<<"个右圆括号匹配的左圆括号!"<<endl;
}
else if(expression[i-1]=='[')
{
s2.Push(i);
}
else if (expression[i-1]==']')
{
if(s2.Pop(j)==true)
cout<<j<<"与"<<i<<"匹配"<<endl;
else
cout<<"没有与第"<<i<<"个右中括号匹配的左中括号!"<<endl;
}
else if (expression[i-1]=='{')
{
s3.Push(i);
}
else if (expression[i-1]=='}')
{
if(s3.Pop(j)==true)
cout<<j<<"与"<<i<<"匹配"<<endl;
else
cout<<"没有与第"<<i<<"个右花括号匹配的左花括号!"<<endl;
}
while(s1.IsEmpty()==false) //栈中还有左括号
{
s1.Pop(j);
cout<<"没有与第"<<j<<"个左括号匹配的右括号!"<<endl;
}
while(s2.IsEmpty()==false)
{
s2.Pop(j);
cout<<"没有与第"<<j<<"个左括号匹配的右括号!"<<endl;
}
while(s3.IsEmpty()==false)
{
s3.Pop(j);
cout<<"没有与第"<<j<<"个左括号匹配的右括号!"<<endl;
}
}
}
int main()
{
SeqStack <int> S(10);
char str1[100]; //字符数组
cout<<"请输入一串带有括号的字符串："<<endl;
cin>>str1;
cout<<"您输入的字符串是："<<endl;
cout<<str1;
int length=strlen(str1);
S.PrintMatchPairs(str1);
system("repause");
return 0;
}