uva673 - Parentheses Balance(栈)

题意：1、空串合法。2、若A和B合法，则AB合法。3、若A合法，则(A)和[A]合法。

思路：遍历串，遇到（或[,则压入队列，若遇到），判断：若栈空，则不合法；若栈顶元素不是(，也不合法。]同理。因为判断的是栈顶元素，所以能成对的左括号都可及时弹出。

注意:1、用gets读，因空串合法。2、遍历后，栈不为空，也不合法。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<sstream>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<algorithm>

#include<stack>

#include<queue>

#include<deque>

#include<set>

#include<map>

#include<list>

using namespace std;

const int MAXN=+;

const int INF=0x7f7f7f7f;

const double PI=acos(1.0);

typedef long long ll;

typedef unsigned long long llu;

char s[];

stack<char> sta;

int main()

{

    int n;

    scanf("%d",&n);

    getchar();//= =

    while(n--)

    {

        bool ans=true;

        while(!sta.empty())//注意将栈清空

            sta.pop();

        gets(s);//注意题意，空串合法

        for(int i=; s[i]; i++)

        {

            if(s[i]=='('||s[i]=='[')//(，[，)，]别打错= =

                sta.push(s[i]);

            else if(s[i]==')')

            {

                if(sta.empty()||sta.top()!='(')

                {

                    ans=false;

                    break;

                }

                sta.pop();

            }

            else if(s[i]==']')

            {

                if(sta.empty()||sta.top()!='[')//top是栈顶元素

                {

                    ans=false;

                    break;//= =

                }

                sta.pop();

            }

        }

        if(!sta.empty()) ans=false;//以上操作会将与之成对的左括号弹出栈，若栈不为空，说明串内有不成对的括号，是不合法的

        printf("%s\n",ans ? "Yes" : "No");

    }

    return ;

}