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

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

    좋은 웹페이지 즐겨찾기