首页 > 代码库 > 平衡的括号Uva-673

平衡的括号Uva-673

技术分享

题意大概:输入一个包括“()”和“[ ]”的括号序列,判断是否合法。具体规则如下:

1.空串合法。

2.如果A和B都合法,那么AB也合法。

3.如果A合法,那么[A]和(A)都合法。

思路:

初始化一个栈,输入序列,然后进行扫描:

1.序列长度肯定是偶数(包括 0);

2.如果是“[”或者“(”则将其压进栈里面;

3.如果是“)”或者“]”,则根据当前栈顶的元素值进行判断,

如果匹配不成功的话,就不用再进行匹配了,肯定是不能成功的!


代码如下:


<span style="font-family:KaiTi_GB2312;font-size:18px;"><strong>#include<cstdio>
#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
const int maxn=201314;
char str[maxn];
stack<char> s;//用来存储左符号的栈
void init()
{
    while(!s.empty())
    s.pop();
}
void solve()
{
    int len=strlen(str);
    if(len%2!=0)//如果len是奇数,证明不可能匹配成功!
    {
        cout<<"No"<<endl;
        return ;
    }
    for(int i=0;i<len;i++)
    {
        if(str[i]=='['||str[i]=='(')
           s.push(str[i]);//如果是(或者[则直接压入栈里面!
        else
        {
            char now=s.top();
            if((now=='('&&str[i]==')')||(now=='['&&str[i]==']'))//如果遇见)或者]符号,则进行判断!
            {
                s.pop();
            }
            else
            {
                cout<<"No"<<endl;
                return ;
            }
        }
    }
    cout<<"Yes"<<endl;
    return ;
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        cin>>str;
        init();
        solve();
    }
    return 0;
}
</strong></span>




平衡的括号Uva-673