글 읽기 - [C] 반례 부탁드립니다..

cyunchaeskku 2년 전 0

반례를 도저히 못 찾겠습니다 ㅠ

도와주시면 정말 감사하겠습니다.

'(' 나 '[' 둘 다 stack_all 안에 집어넣어 SPeek하면서 어떤 것을 먼저 pop해야 옳은 순서인지 체크할 수 있도록 했습니다.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define STACK_LEN 102

typedef char Data;

typedef struct _arrayStack
{
    Data stackArr[STACK_LEN];
    int topIndex;
} ArrayStack;

typedef ArrayStack Stack;

void StackInit(Stack *pstack)
{
    pstack->topIndex=-1;
}
int SIsEmpty(Stack *pstack)
{
    if(pstack->topIndex==-1)
        return TRUE;
    else
        return FALSE;
}
void SPush(Stack *pstack, Data data)
{
    pstack->topIndex++;
    pstack->stackArr[pstack->topIndex] = data;
}
Data SPeek(Stack *pstack)
{
    if(SIsEmpty(pstack))    return -1;
    else
    return pstack->stackArr[pstack->topIndex];
}
Data SPop(Stack *pstack)
{
    int rIdx;
    if(SIsEmpty(pstack))    return -1;
    else
    {
        rIdx=pstack->topIndex;
        pstack->topIndex--;
        return pstack->stackArr[rIdx];
    }

    
}
int Size(Stack *pstack)
{
    return pstack->topIndex+1;
}

int main()
{
    int flag=1; // 1이면 대칭
    Stack stack_small;
    StackInit(&stack_small);
    Stack stack_big;
    Stack stack_all;
    StackInit(&stack_big);
    char c[102];
    int priority=0; // 0이면 소괄호를 먼저 pop해야 되는 순서. 
    
    while(1)
    {
        flag=1;
        StackInit(&stack_small);
        StackInit(&stack_big);
        StackInit(&stack_all);
        gets(c);
        int l=strlen(c);
        if(l==1 && c[0]=='.')    break;
        for(int i=0;i<l-1;i++)
        {
        if(c[i]=='(')
        {
            SPush(&stack_small,c[i]);
            SPush(&stack_all,c[i]);
        }
        else if(c[i]=='[')
        {    
            SPush(&stack_big,c[i]);
            SPush(&stack_all,c[i]);
        }
        else if(c[i]==')')
        {
            if(SIsEmpty(&stack_small)==1)
            {
                printf("no\n");
                flag=0;
                break;
            }
            else
            {
                if(SPeek(&stack_all)=='(')  priority=0;
                else priority=1;
                if(priority==0) {SPop(&stack_small);SPop(&stack_all);}
                else 
                {
                    printf("no\n");
                    flag=0;
                    break;
                }
            }
        }
        else if(c[i]==']')
        {
            if(SIsEmpty(&stack_big)==1)
            {
                printf("no\n");
                flag=0;
                break;
            }
            else
            {
                if(SPeek(&stack_all)=='(')   priority=0;
                else priority=1;

                if(priority==1) {SPop(&stack_big);SPop(&stack_all);}
                else
                {
                    printf("no\n");
                    flag=0;
                    break;
                }
            }
        }
        }
        if(SIsEmpty(&stack_small)==0 || SIsEmpty(&stack_big)==0)
            flag=0;
        if(flag==1) printf("yes\n");
        else {}
        c[0]='\0';
    }

    
    



}

dbshin59 2년 전 1

input: ()

output :

answer: yes

input: (

output: yes

answer: no

input: )

output: yes

answer: no

정도 됩니다.

cyunchaeskku 2년 전 0

dbshin59님, 정말 감사합니다 ㅠ 소괄호 하나만 들어오는 경우를 생각 못 했네요. 정말 감사합니다!! 덕분에 해결했습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[C] 반례 부탁드립니다..

cyunchaeskku 2년 전 0

dbshin59 2년 전 1

cyunchaeskku 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말