PGR21.com
이전 질문 게시판은 새 글 쓰기를 막았습니다. [질문 게시판]을 이용바랍니다.
Date 2010/04/16 03:52:36
Name 제로스
Subject C언어 질문입니다.
정규식표현 구현이 너무 힘들어서 도움을 얻고자합니다..

우선 *와 ?와 알파벳이 정규 표현의 입력 패턴의 전부입니다.

#include<stdio.h>
#include<ctype.h>
#include<string.h>
#define SIZE 20

void closetest(int state);

int main()
{
        char str[SIZE];
        char word[SIZE];
        char ch;
        unsigned int i,j;

                FILE *file=fopen("c:\\sample1.txt","r");
        FILE *file1=fopen("c:\\sample2.txt","w");
        if(file==NULL){
                printf("file open error!\n");
                return 1;
        }

        printf("단어를 입력하세요:");
        scanf("%s",word);

        while(!feof(file)){
                ch=fgetc(file);
                if(isalpha(ch)==0)
                        ch=' ';
                fputc(ch,file1);
        }

        closetest(fclose(file));
        closetest(fclose(file1));

        file1=fopen("c:\\sample2.txt","r");
        if(file==NULL){
                printf("file open error!\n");
                return 1;
        }

        while(!feof(file1)){
                fscanf(file1, "%s", str);
                j=0;
                for(i=0;i<strlen(str);i++){
                        for(;j<strlen(word);j++){
                        }
                }
        }

        closetest(fclose(file1));

        return 0;
}

void closetest(int state){
        if(state!=0){
                printf("file close error!\n");
        }
}

일단 파일에서 단어까지는 찾았습니다.

for(i=0;i<strlen(str);i++){
        for(;j<strlen(word);j++){

그다음에 str이 word패턴에 맞는지 검사하려고 하는데 .. 몇시간을 끙끙앓아도 도저히 답이 안나오네요 ..

다른 친구에게 물어보는 자기는 for문 8개를 지지고 볶고해서 만들었다고 하는데 ..

도저히 생각해도 답이 나오지 않네요 ..

늦은시간에 질문해서 도움주실분이 계실지 모르겠지만 .. 그래도 한번 올려봅니다.

통합규정 1.3 이용안내 인용

"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.
법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
아이온
10/04/16 04:39
수정 아이콘
여기는 늦은 시간이 아니라서 답을 달아 봅니다. 우선 데드라인이 언제인가요? 저는 학부 때 한 과목을 재수강 한 적 있습니다. 초수강 땐 바쁘다는 핑계로 책 한 번 정독하지 않고 프로젝트부터 덤볐다가 3일 밤 새고 1/7도 못 끝내고 포기했습니다. 컴퓨터 과목이었고, 이미 당시에 나름 컴퓨터 좀 한다고 생각했었는데 좌절했었습니다. 재수강 때 차분히 며칠 들여서 텍스트 정독하고, 초수강 시절 숙제보다 업그레이드 된 것을 처리하는 데, 전체 다 해서 이틀 반이 걸렸습니다.

억지로 "숙제부터" 어떻게든 한다고 실력이 크게 늘지 않는다고 생각합니다. 누군지 기억은 나지 않는데, 어느 유명한 한국인 프로그래머가 컴퓨터가 늘려면 컴퓨터를 멀리 하(고 책상을 가까이 하)라고 쓴 적이 있습니다.

이 문제는 아주 단순하고 교과서적인 오토마타 문제입니다. 따라서 오토마타 책이나 컴파일러 책에서 NFA, NFA to DFA를 조금만 정독하셔도 어떻게 프로그램을 하셔야 하는지 알 수 있습니다. FSM을 논리회로 시간에, 오토마타를 오토마타 시간에 배우지 않나요? 혹시 둘다 모르신다면 덧글로 메모를 남겨주세요.
10/04/16 08:31
수정 아이콘
어렵게 풀면 어렵고 쉽게 풀면 쉬운 문제입니다.
순차적으로 접근을 하자면 '?' '*"를 제외한 상태에서 표현식에 부합하는지 검사하는 함수를 작성해 보겠습니다.
int check(char *word, char *exp)

if( strlen(word)==0&&
strlen(exp)==0 )return 1;

if(word[0]==exp[0])
return check(word+1,exp+1);
return 0;

그냥 두단어가 일치하는지 검사하는 역할을 합니다. check("starcraft","starcraft")는 1을 반환합니다.

여기에 '?'를 구현하고 싶다면
if(exp[0]=='?')
return check(word,exp+1)||check(word+1,exp+1);
이렇게 추가하면 됩니다.
'?'의 정의 대로 0개의 임의의 문자라면 check(word,exp+1)에서, 1개의 임의의 문자라면 check(word+1,exp+1)에서 1을 반환합니다.
여기까지 추가하면 check("starcraft","st???cra??") 같은 표현식을 검사할수 있습니다.

'*'를 구현하는 것도 '?'와 비슷합니다. 0~n의 임의의 문자라는 정의에 부합하게 하려면
if(exp[0]=='*')

if(strlen(word)!=0)return check(word,exp+1)||check(word+1,exp);
else return check(word,exp+1);

이런식으로 작성하면 됩니다.
check(word+1,exp)는 '*'가 n개의 문자로 확장되는 경우를 검사하며
check(word,exp+1)는 '*'가 더이상 확장되지않는 경우를 검사합니다.
지난번에 '*'만 구현해 드렸는데 결과가 제대로 나와서 지나갔는데
다시 보니 word이후의 위치를 참조할 가능성이 있으니 이부분은 이번 코드를 사용하세요.

정리하자면
int check(char *word, char *exp)

if( strlen(word)==0&&
strlen(exp)==0 )return 1;

if(word[0]==exp[0])
return check(word+1,exp+1);

if(exp[0]=='?')
return check(word,exp+1)||check(word+1,exp+1);

if(exp[0]=='*')
{
if(strlen(word)!=0)return check(word,exp+1)||check(word+1,exp);
else return check(word,exp+1);


return 0;
}

이 함수를 check("starcraft","s*r*a??"); 이런 식으로 사용하면 됩니다. 작성하신 코드에서check(str,word)호출하면 검사후 1이나 0을 반환할 겁니다.
목록 삭게로! 맨위로
번호 제목 이름 날짜 조회
79307 신랑이 신부에게 불러줄만한 노래 추천 부탁드립니다. [12] 바가지다2644 10/04/16 2644
79306 인간관계에 대한 질문입니다. [2] 깐따삐야2361 10/04/16 2361
79305 여고 3학년생이 학교에서 볼만한 다큐멘터리 추천해 주세요. [19] 은유2768 10/04/16 2768
79304 예능결방으로 방송국들이 얻는 이점이 있나요? [5] 이슬라나2487 10/04/16 2487
79303 아이폰 쓰시는분 온게임넷이나 엠비시게임 보는 법 없나요 [4] Mraz3161 10/04/16 3161
79302 재미있는 횡 스크롤 게임 없을까요? [9] 나나시코2925 10/04/16 2925
79301 여러분이 생각하시는 가장 감동적인 스타리그 준우승 장면은 무엇인가요? [21] Xell0ss2493 10/04/16 2493
79300 롯데월드 주말엔 역시 아비규환이지요? [7] 삭제됨3458 10/04/16 3458
79299 C언어 질문입니다. [9] 제로스2748 10/04/16 2748
79298 호텔이용에 대해서 질문드립니다~ [16] 삭제됨2440 10/04/16 2440
79297 쉬운 영작 질문입니다. [6] zeros1929 10/04/16 1929
79296 오늘자 아이스쇼 표를 급하게 팔아야 하는데요.. [3] neRo2303 10/04/16 2303
79294 컴퓨터 소음 해결방법중 어느게 좋을지 질문해봅니다. [11] 현미녹차2159 10/04/15 2159
79293 컴퓨터가 바이러스에 걸렸습니다. 살려주세요 -_-; [7] 읭?2483 10/04/15 2483
79292 c질문입니다. [3] 제로스1929 10/04/15 1929
79291 원피스질문드려요 [8] 옥희2230 10/04/15 2230
79290 태어나서 택배를 부쳐본적이 없는데..;; [3] 민죽이2097 10/04/15 2097
79289 경제학원론 문제들만 모아놓은 것을 없을까요?? 하성현2174 10/04/15 2174
79288 클래식 노래를 찾아주세요~!! [2] ILikeOOv2145 10/04/15 2145
79287 홍삼액 질문입니다. [2] ROKZeaLoT2095 10/04/15 2095
79286 야구 티켓 예매시 오류가 뜨네요? 배레모2656 10/04/15 2656
79285 파티가 위주인 온라인 게임좀 추천 해주세요. [21] 이디어트3278 10/04/15 3278
79284 천안함 침몰 원인이 어뢰쪽으로 결론이 나는 분위기로 가는데, 확실한 이유가 있나요? [6] 벤카슬러2431 10/04/15 2431
목록 이전 다음
댓글

+ : 최근 6시간내에 달린 댓글
+ : 최근 12시간내에 달린 댓글
맨 위로