/*

括号匹配问题，比较经典，利用堆栈来实现(摘自internet)

1. 括号匹配的四种可能性：

①左右括号配对次序不正确

②右括号多于左括号

③左括号多于右括号

④左右括号匹配正确

2. 算法思想：

顺序扫描算数表达式（表现为一个字符串），当遇到三种类型的左括号时候让该括号进栈；

当扫描到某一种类型的右括号时，比较当前栈顶元素是否与之匹配，若匹配，退栈继续判断；

若当前栈顶元素与当前扫描的括号不匹配，则左右括号配对次序不正确；

若字符串当前为某种类型的右括号而堆栈已经空，则右括号多于左括号；

字符串循环扫描结束时，若堆栈非空（即堆栈尚有某种类型的左括号），则说明左括号多于右括号；

否则，括号配对正确。

3. 程序实现：

*/

#include <iostream>

using namespace std;

#define maxsize 100

struct 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;

}