취미 프로 그래 밍: 문자열 에서 정보 추출 (정 답 참조 - 상)

이번 '취미 프로 그래 밍' 의 목적 은 문자열 을 해석 하고 지정 한 패턴 의 문자열 에서 정 보 를 추출 하 는 것 이다.현재 이 문제 에 대해 해결 방안 은 여러 가지 가 있 습 니 다. 예 를 들 어 직접 나 누고 정규 표현 식 을 사용 하거나 지금 본 논문 처럼 순서대로 해석 합 니 다.전체적인 결과 에 있어 이런 방법 은 모두 바람 직 하 다. 그러나 지금 제 가 제시 하고 자 하 는 방법 은 가장 '전형 적' 이 고 '학습' 과 '표현' 가치 가 있 는 해결 방안 이 라 고 생각 합 니 다. 상태 기 를 바탕 으로 하 는 순서 문자 분석 입 니 다.다른 방법 에 대해 서도 심도 있 게 분석 하 시 는 것 을 환영 합 니 다.
문자열 해석 의 구체 적 인 규칙 을 다시 읽 어야 할 수도 있 습 니 다. 처음에는 다음 세 가지 만 요약 할 수 있 습 니 다.

하나의 text 는 하나 에서 여러 개의 token group 로 구성 된다.하나의 token group 은 하나 이상 의 token 으로 구성 되 어 있다.

token group 의 token 간 에 하나의 횡선 "-" 을 사용 하여 분할 합 니 다.text 의 token group 사이 에 두 개의 가로 선 "-" 을 사용 하여 분할 합 니 다.

token 은 작은 따옴표 소 포 를 사용 할 수 있 습 니 다. 작은 따옴표 소포 안의 횡선 은 일반 문자 로 처리 하고 작은 따옴표 소포 안에 두 개의 작은 따옴표 로 하나의 따옴표 를 표시 합 니 다.

최종 결 과 는 text 문자열 을 token group 목록 으로 나 누 는 것 입 니 다.

static List<List<string>> Parse(string text) { ... }

여기 서 우 리 는 List 를 사용 하여 token group (즉 token 목록) 을 표시 합 니 다.자 연 스 럽 게 표현 방식 이 다 를 수 있다.예 를 들 어 Parse 방법 은 '목록 의 배열', '배열 의 목록' 또는 '배열 의 배열' 을 되 돌려 주 는 데 문제 가 없습니다.
다음 방법 은 winter - cn 이 지난 글 뒤의 답장 을 바탕 으로 간단 한 수정 과 주석 을 한 후에 얻 은 결 과 를 바탕 으로 합 니 다.이 방법의 사고방식 은 내 가 문 제 를 낼 때 이미 준비 한 '참고 답안' 과 약속 이나 한 듯 이 일치 하지만 winter - cn 의 실현 은 나의 것 보다 더욱 간단 하 다. 그래서 나의 코드 는 추 태 를 보이 지 않 는 다. 우 리 는 지금 고수 의 노동 성 과 를 감상 하 러 왔 다.
winter - cn 의 방법 은 '해석' 작업 을 5 가지 상태 로 나 누 는 것 입 니 다. 각 상 태 는 하나의 해석 논리 에 대응 하고 모든 해석 논 리 는 현재 문 자 를 처리 하 는 것 외 에 다음 문자 가 사용 하 는 '해석 논리' 를 되 돌려 줍 니 다. 이것 이 바로 상태의 이전 입 니 다.winter - cn 기 존의 방법 은 Func 를 사용 하여 논 리 를 해석 하 는 유형 을 표시 하 는 것 입 니 다. 이렇게 하면 새로운 상 태 를 얻 을 때마다 Func 로 전환 해 야 합 니 다.그러나 이러한 논 리 를 더욱 명확 하 게 표현 하기 위해 우 리 는 자신의 유형 으로 돌아 가 는 '재 귀' 의뢰 유형 도 정의 할 수 있다.

delegate StateParser StateParser(char ch);

현재 의 실현 에서 우 리 는 그것 의 해석 과정 을 5 개의 상태 로 분해 하여 각각 다른 '시각' 에서 의 해석 논리 에 대응한다.

static List<List<string>> Parse(string text)
{
    StateParser p1 = null; //     token     
    StateParser p2 = null; //           “-”      
    StateParser p3 = null; //     token              
    StateParser p4 = null; //          token  
    StateParser p5 = null; //          token  

    var currentToken = new StringBuilder(); //        token（     ）
    var currentTokenGroup = new List<string>(); //        token group（   token）
    var result = new List<List<string>>(); //       （   token group）
    ...

    return result;
}

p1 부터 p5 까지 는 이른바 '상태', 즉 '논리 해석' 입 니 다. 모두 currentToken, currentToken Group 과 result 세 개의 데 이 터 를 조작 하고 다음 상 태 를 되 돌려 줍 니 다.상태의 구분 은 한 가지 만 있 는 것 이 아니 라 서로 다른 상태 구분 방식 이 서로 다른 논 리 를 형성 할 수 있다.우 리 는 다음 에 이러한 구분 방식 에 따라 모든 상태 지정 을 실현 해 야 한다.실현 하 는 과정 에서 우 리 는 '현재' 상태의 논리 적 세부 사항 과 다른 상태의 직책 을 항상 지 켜 야 한다. 이렇게 상태의 이전 을 실현 하 는 것 도 어 려 운 일이 아 닌 것 같다.
우선 p1 입 니 다. token 의 첫 번 째 문 자 를 해석 하 는 역할 을 합 니 다.

//   token     
p1 = ch =>
{
    if (ch == '-')
    {
        //   token         “-”，
        //     token                    
        throw new ArgumentException();
    }

    if (ch == '\'')
    {
        //           ，
        //           token  
        return p5;
    }
    else
    {
        //        ，     token   ，
        //           token  
        currentToken.Append(ch);
        return p4;
    }

};

이 어 p2: 구분자 "-" (작은 따옴표 패키지 에 있 는 "-" 는 포함 되 지 않 음) 를 분석 한 다음 문자 입 니 다.

//         “-”      
p2 = ch =>
{
    if (ch == '-')
    {
        //        “-”，    token group   （         “-”），
        //      token group     ，      token group
        result.Add(currentTokenGroup);
        currentTokenGroup = new List<string>();
        return p1;
    }
    else if (ch == '\'')
    {
        //           ，     token      
        //           token  
        return p5;
    }
    else
    {
        //        ，     token   ，
        //           token  
        currentToken.Append(ch);
        return p4;
    }
};

다음은 p3: token 내부 나 끝 에 있 는 작은 따옴표 의 다음 문 자 를 분석 합 니 다.

//   token               
p3 = ch =>
{
    if (ch == '\'')
    {
        //           ，          ，
        //     token    “  ”   ，    token         ，
        //            token  
        currentToken.Append('\'');
        return p5;
    }
    else if (ch == '-')
    {
        //             ，      token     
        //      token    token group，    token，
        //              
        currentTokenGroup.Add(currentToken.ToString());
        currentToken = new StringBuilder();
        return p2;
    }
    else
    {
        //                       ，
        //         ，     
        throw new ArgumentException();
    }
};

마지막 으로 p4 와 p5 입 니 다. 일반적인 token 과 따옴표 로 포 장 된 token 문 자 를 처리 하 는 데 사 용 됩 니 다.

//          token  ，
//          （       ） token
p4 = ch => 
{
    if (ch == '\'')
    {
        //   token       ，     
        throw new ArgumentException();
    }

    if (ch == '-')
    {
        //         ，     token   ，
        //      token    token group，    token，
        //             
        currentTokenGroup.Add(currentToken.ToString());
        currentToken = new StringBuilder();
        return p2;
    }
    else
    {
        //       ，   token        
        //          token  
        currentToken.Append(ch);
        return p4;
    }
};

//          token  
p5 = ch =>
{
    if (ch == '\'')
    {
        //          token        ，
        //           ，         
        return p3;
    }
    else
    {
        //       ，      token 
        currentToken.Append(ch);
        return p5;
    }
};

이러한 상태 에서 의 논 리 는 모두 하나의 특징 을 가지 고 있 습 니 다. 그들 은 모두 C \ # 컴 파일 러 로 형 성 된 패 킷 을 통 해 '외부' 상 태 를 조작 합 니 다. 그러나 이 '외부' 는 이러한 익명 함수 의 외 부 를 말 하지만 모두 Parse 방법 자체 에 속 합 니 다!이것 은 우리 의 상태 가 '순수 함수' 가 아니 지만 Parse 방법 은 어떠한 부작용 도 없다 는 것 을 의미한다. (Side Effect, 즉 반환 값 을 제외 하고 다른 외부 상태 와 같은 반환 값 이 영원히 같은 결과 에 영향 을 주지 않 는 다 는 것 이다.)이 특징 은 Parse 방법 이 여러 스 레 드 에서 동시에 호출 될 수 있 도록 확보 했다.winter - cn 의 방법 은 C \ # 컴 파일 러 의 특성 을 교묘 하 게 사용 하여 Parse 방법의 실현 을 간소화 했다.
5 가지 상 태 를 정의 한 후에 우 리 는 p1 부터 문자열 의 모든 문 자 를 순서대로 처리 하고 상태 가 바 뀌 면서 모든 문자 의 논 리 를 처리 해 야 합 니 다.물론 마지막 '마무리' 작업 도 빠 질 수 없다.

static List<List<string>> Parse(string text)
{
    ...

    text.Aggregate(p1, (sp, ch) => sp(ch));

    currentTokenGroup.Add(currentToken.ToString());
    result.Add(currentTokenGroup);

    return result;
}

이 를 통 해 알 수 있 듯 이 이런 방법의 장점 중 하 나 는 완전한 '순서 처리' 로 한 번 만 옮 겨 다 니 는 것 이다.문자열 의 분할 이나 정규 표현 식 을 사용 하여 해석 하면 보통 '역 추적' 과 더 많은 문자열 을 나 눌 수 있 습 니 다.따라서 이 방법 은 성능 적 으로 도 어느 정도 장점 이 있 을 것 으로 추정 되 지만 실제 성능 을 비교 해 야 정확 한 결 과 를 얻 을 수 있다.본문 의 모든 코드 는 이미 저장 되 어 있다.http://gist.github.com/214427복사, 실행, 디 버 깅 등 을 할 수 있 습 니 다.
이번 '취미 프로 그래 밍' 은 지금까지 가장 시끌벅적 한 것 입 니 다. 지난 글 의 답장 에서 많은 친구 들 이 내 놓 은 대량의 해결 방안 을 발견 할 수 있 습 니 다. 그러나 시간 과 정력 이 유한 하기 때문에 저 는 일일이 조회 할 수 없습니다.또한, winter - cn 은 제 생각 과 가 깝 지만 더 좋 은 방법 을 제 시 했 기 때문에 나중에 저 는 F \ # 로 다른 사고방식 의 버 전 을 실 현 했 습 니 다. F \ # 일부 언어 특성 이 문자열 분석 작업 에 매우 적합 한 것 같 습 니 다. 이것 은 저희 가 C \ # 코드 를 작성 하 는 데 도 참고 가치 가 있 습 니 다.