/*括号匹配问题，比较经典，利用堆栈来实现(摘自internet)1. 括号匹配的四种可能性：①左右括号配对次序不正确②右括号多于左括号③左括号多于右括号④左右括号匹配正确2. 算法思想：顺序扫描算数表达式（表现为一个字符串），当遇到三种类型的左括号时候让该括号进栈；当扫描到某一种类型的右括号时，比较当前栈顶元素是否与之匹配，若匹配，退栈继续判断；若当前栈顶元素与当前扫描的括号不匹配，则左右括号配对次序不正确；若字符串当前为某种类型的右括号而堆栈已经空，则右括号多于左括号；字符串循环扫描结束时，若堆栈非空（即堆栈尚有某种类型的左括号），则说明左括号多于右括号；否则，括号配对正确。3. 程序实现：*/#include <iostream>using namespace std;#define maxsize 100struct sStack{     char sign[maxsize];     int top;};int InitsStack(sStack &SS){     SS.top=-1;     return 1;}int IsEmptysStack(sStack &SS){     if(SS.top==-1)         return 1;     return 0;}int PushsStack(sStack &SS,char c){     SS.sign[++SS.top]=c;     return 1;}int UpsStack(sStack &SS){    if(IsEmptysStack(SS))    {         cout<<"栈空"<<endl;         return 0;    }    SS.top--;    return 1;}char TopsStack(sStack &SS){    if(IsEmptysStack (SS))    {         cout <<"栈空"<<endl;         return 0;    }    return SS.sign[SS.top];}int main(){     string s;     cout<<"输入表达式：";     cin>>s;     int length=s.length();     int i;     sStack SS;     InitsStack(SS);     for(i=0;i<length;++i)     {           if(s[i]==‘(‘||s[i]==‘[‘||s[i]==‘{‘)                    PushsStack(SS,s[i]);           else if(s[i]==‘)‘&&!IsEmptysStack(SS)&&TopsStack(SS)==‘(‘)                UpsStack(SS);                    else if(s[i]==‘)‘&&!IsEmptysStack(SS)&&TopsStack(SS)!=‘(‘)                    cout<<"括号匹配次序不正确"<<endl;           else if(s[i]==‘]‘&&!IsEmptysStack(SS)&&TopsStack(SS)==‘[‘)                    UpsStack(SS);           else if(s[i]==‘]‘&&!IsEmptysStack(SS)&&TopsStack(SS)!=‘[‘)                    cout<<"括号匹配次序不正确"<<endl;           else if(s[i]==‘}‘&&!IsEmptysStack(SS)&&TopsStack(SS)==‘{‘)                    UpsStack(SS);           else if(s[i]==‘}‘&&!IsEmptysStack(SS)&&TopsStack(SS)!=‘{‘)                    cout<<"括号匹配次序不正确"<<endl;           else if((s[i]==‘)‘||s[i]==‘]‘||s[i]==‘}‘)&&IsEmptysStack(SS))                    cout<<"右括号多于左括号"<<endl;     }     if(!IsEmptysStack(SS))           cout<<"左括号多于右括号"<<endl;     else if(i=(length-1)&&IsEmptysStack(SS))           cout<<"括号匹配正确"<<endl;                    system("PAUSE");     return 0;}