NYOJ 2 괄호 짝 짓 기 문제 (데이터 구조)

질문
시간 제한:
3000 ms  |  메모리 제한:
65535 KB
난이도:
3
묘사 하 다.
현재 괄호 서열 이 있 습 니 다. 이 괄호 가 맞 는 지 확인 하 십시오.
입력
첫 번 째 줄 에 N (0 < N < = 100) 을 입력 하면 N 조 테스트 데이터 가 있 음 을 표시 합 니 다.다음 N 줄 에 여러 개의 입력 데 이 터 를 입력 합 니 다. 각 그룹의 입력 데 이 터 는 하나의 문자열 S (S 의 길 이 는 10000 이하 이 고 S 는 빈 문자열 이 아 닙 니 다) 입 니 다. 테스트 데이터 그룹 수 는 5 그룹 보다 적 습 니 다. 데이터 보증 S 에는 "["] "," (")" 네 가지 문자 만 포함 되 어 있 습 니 다.
출력
각 그룹의 입력 데이터 의 출력 이 한 줄 을 차지 합 니 다. 이 문자열 에 포 함 된 괄호 가 짝 을 이 루 면 Yes 를 출력 하고, 짝 을 이 루 지 않 으 면 No 를 출력 합 니 다.
샘플 입력

3
[(])
(])
([[]()])

샘플 출력

No
No
Yes

근원
네트워크
업로드 자
naonao
    원리: 기대 의 급박 도
1. 데이터 구조 책 에 있 는 것 을 보면 귀찮아 서 추천 하지 않 습 니 다.

#include<stdio.h>
#include<stdlib.h>
typedef struct{
    char m[10000];    
    int last;
}Seqlist;
void Inlist(Seqlist *L){  
    L->last=-1;}       //  
void push(Seqlist *L,char num){
    L->m[++(L->last)]=num;}       //  
void pop(Seqlist *L,char *num){
    *num=L->m[L->last];
    L->last--;
}                    //   
int isempty(Seqlist *L){
    return (L->last==-1?1:0);
}                  // yes or no

int main()
{
    char tem,t;    
    char *tt=&t;
    int i,ll[5],k=-1,h,flag=1;   //i        ll[5]  yes no
    Seqlist L;    //   L
    Inlist(&L);    ////  
    scanf("%d",&i);    //      
    if(i>5)
        return 0;  //     5 
    while(i-->0)
    {
        flag=1;    
        while(L.last!=-1)
            pop(&L,tt);
        fflush(stdin);  //       
        while((tem=getchar())!='
')
        {        
            if(isempty(&L))    
            {
                if(tem!='('&&tem!='[')    
                {
                    ll[++k]=0;    
                    flag=0;break;
                }
                else
                    push(&L,tem);
            }//empty
            else if(tem==')')
            {
                pop(&L,tt);
                if(*tt!='(')
                {
                    ll[++k]=0;
                    flag=0;break;
                }
            }
            else if(tem==']')
            {
                pop(&L,tt);
                if(*tt!='[')
                {
                    ll[++k]=0;
                    flag=0;break;
                }
            }
            else if(tem=='['||tem=='(')
                push(&L,tem);
        }//while1
        if(flag)
        {
            if(isempty(&L))
            ll[++k]=1;
            else ll[++k]=0;
        }
    }    
    for( h=0;h<=k;h++)    
    {    
        if(ll[h]==0)printf("No
");    
        if(ll[h]==1) printf("Yes
");    
    }    
   return 0;    
}

 
2. 생각 이 생기 면 다시 3 을 보 러 간다.
  

 #include<stdio.h>  

    #include<string.h>  

    #include<stdlib.h>  

    int main()  

    {  

        char a[10100],b[10100];  

        int n,len,i,top;  

        scanf("%d",&n);  

        while(n--)    

        {  

            scanf("%s",a);  

            len=strlen(a);  

            top=1;   

            b[0]=a[0];    //    

            for(i=1;i<len;i++)  //i 1     

            {  

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

                  b[top++]=a[i];//      

                if(a[i]==')')  

                {  

                    if(b[top-1]=='(')   //   ！！！ 

                       top--;//         

                    else    

                       b[top++]=a[i];  

                }  

                if(a[i]==']')      //   

                {  

                    if(b[top-1]=='[')  

                      top--;  

                    else  

                      b[top++]=a[i];   

                }   

            }  

            if(top==0)  //         ，           

                printf("Yes
");  

            else  

                printf("No
");  

        }  

        return 0;  

    }  

3. 코드 간소화:

#include<stdio.h>
#include<string.h>
int main(){
	int n,i,flag;
	char a[10005];
	scanf("%d
",&n);
	while(n--){
		flag=1;
		memset(a,0,sizeof(a));
		scanf("%c",&a[0]);
		i=1;
		while(scanf("%c",&a[i])&&(a[i]=='['||a[i]==']'||a[i]=='('||a[i]==')' ) ){//   
			 if(a[i]==']')
			 	if(a[i-1]=='[') i-=2;//    ，    ，        ，          
			 	else   flag=0; //    ，No 
			 if(a[i]==')')
			 	if(a[i-1]=='(')  i-=2; //    ，    ，        ，          
				else   flag=0;  //    ，No 
			 i++;//     ‘[ ’  ‘( ’ ，     
		}
		if(flag==1&&i==0) printf("Yes
");//      ，       Yes 
		else printf("No
");//  No 
	}
	return 0;
}