首页 > 代码库 > 括号配对问题

括号配对问题

括号配对问题

时间限制:3000 ms  |  内存限制:65535 KB

难度:3

描述

现在,有一行括号序列,请你检查这行括号是否配对。

输入

第一行输入一个数N(0<N<=100),表示有N组测试数据。后面的N行输入多组输入数据,每组输入数据都是一个字符串S(S的长度小于10000,且S不是空串),测试数据组数少于5组。数据保证S中只含有"[","]","(",")"四种字符

输出

每组输入数据的输出占一行,如果该字符串中所含的括号是配对的,则输出Yes,如果不配对则输出No

样例输入

3

[(])

(])

([[]()])

样例输出

No

No

Yes

 

程序代码:

利用字符数组。。。

#include<stdio.h>

#include<stdlib.h> 

int main()

{

  int n,len,t;

  char a[10000],m;

  scanf("%d",&n);

  getchar();

  while(n--)

  {

    len=0;

    m=getchar();

    while(m!=‘\n‘)

    {

      t=0;

      if(m==‘)‘&&a[len-1]==‘(‘  ||  m==‘]‘&&a[len-1]==‘[‘)

      {     //若当前的字符与其前的字符相匹配时,将len减1 

        t=1;   

        len--;

      }  

      if(t==0)//如果是字符‘(‘,‘[‘,时,存放在数组a中,当满足括号配对,则将当前a[len]的值重新覆盖 

        a[len++]=m;

      m=getchar();   

    }

   if(len==0)

     printf("Yes\n");

   else

     printf("No\n");

 }

 system("pause");

 return 0;

}

 

利用数据结构栈。。。

#include <iostream>  

#include <stack>  

#include <string>  

using namespace std;  

  

int main()  

{  

    int N;  

    cin>>N;  

    while(N--)  

    {  

        string a;  

        stack<char> s;  

        cin>>a;  

        for(int i=0;i<a.size();i++)  

        {  

            if(a[i]==‘(‘||a[i]==‘[‘)  

                s.push(a[i]);  

            else if(a[i]==‘)‘)  

            {  

                if(!s.empty()&&s.top()==‘(‘)  

                    s.pop();  

                else  

                    s.push(a[i]);  

            }  

            else if(a[i]==‘]‘)  

            {  

                if(!s.empty()&&s.top()==‘[‘)  

                    s.pop();  

                else  

                    s.push(a[i]);  

            }  

        }  

        if(s.empty())  

            cout<<"Yes"<<endl;  

        else  

            cout<<"No"<<endl;         

    }  

    return 0;  

}