[Algorithm / C++] String을 파싱하는 3가지 방법

 

 

문자열 파싱 알고리즘

 

 

String 처리와 관련된 알고리즘 문제를 해결하는 과정에서 종종 Sub String을 파싱해서 처리해야 하는 상황에 직면하곤 합니다. 사실 파싱하는 방법은 머릿속으로 방법을 그리는 것은 쉽다고 생각할 수 있지만 직접 만들어보지 않으면 생각보다 어려울 수도 있습니다. 그래서 이번 포스팅에서는 알고리즘 문제를 해결하기 위해 반드시 필요한 문자열 파싱 알고리즘에 대해 다루고자 합니다.

 

문자열을 파싱하는 방법은 정말 다양합니다. 언어에 따라서는 기본적으로 파싱 기능을 제공하기도 합니다. Java가 대표적으로 파싱을 위한 tokenizer기능을 제공하고 있습니다. C++의 경우에는 공식적으로 STL을 통한 파싱 알고리즘은 아직 제공하지 않고 있습니다. (다만 시간 포맷으로 구성된 string 데이터의 경우 std::chrono 를 통해서 파싱할 수 있도록 별도로 기능을 제공하고 있습니다(STL 기준). 추후에 다룰 기회가 있으면 다루도록 하겠습니다.) 따라서 직접 구현해야 합니다. 본 포스팅에서는 구현 가능한 몇 가지 방법에 대해 소개하도록 하겠습니다.

 

 

Position 지정을 통한 파싱 방법

 

 

가장 대표적인 방법으로 STL String 라이브러리의 find 관련 함수를 이용하는 방법입니다. find와 관련하여 다양한 함수들이 이미 구현되어있는데, find_first_of와 find_first_not_of 를 잘 활용하기만 해도 충분히 파싱 기능을 구현할 수 있습니다. 두 함수는 각각 다음과 같이 오버로딩 함수를 제공합니다.

 

#find_first_of:
string (1)	
size_t find_first_of (const string& str, size_t pos = 0) const noexcept;
c-string (2)	
size_t find_first_of (const char* s, size_t pos = 0) const;
buffer (3)	
size_t find_first_of (const char* s, size_t pos, size_t n) const;
character (4)	
size_t find_first_of (char c, size_t pos = 0) const noexcept;

# find_first_not_of:
string (1)	
size_t find_first_not_of (const string& str, size_t pos = 0) const noexcept;
c-string (2)	
size_t find_first_not_of (const char* s, size_t pos = 0) const;
buffer (3)	
size_t find_first_not_of (const char* s, size_t pos, size_t n) const;
character (4)	
size_t find_first_not_of (char c, size_t pos = 0) const noexcept;

 

- find_first_of: 문자열 str의 위치를 pos 부터 탐색하여 찾은 위치를 리턴

- find_first_not_of: 문자열 str을 제외한 나머지 문자를 pos 부터 탐색하여 찾은 위치를 리턴

 

위 함수의 특성을 이용하여 sub string을 파싱하기 위한 문자열의 포지션을 탐색해야 합니다. 그 전에 포지션을 정하기 위해 그 기준을 정의해야 하는데 다음과 같이 정의할 수 있습니다.

- First Position(이하 Fpos): 구획문자(delimiter)가 아닌 첫 문자의 위치. find_first_not_of 를 사용하여 탐색.

- Last Position(이하 Lpos): 구획문자의 위치. find_first_of 를 사용하여 탐색.

 

이제 위에서 정의한 Fpos와 Lpos를 찾고 그 사이의 sub string을 추출하기한 하면 됩니다. 처음 Fpos와 Lpos를 찾았으면, 다음 sub string을 찾기 위해 2번째 Fpos의 위치 탐색 시작 지점을 이전 Lpos로 정하면 됩니다. 그리고 또 2번째 Lpos를 찾습니다. 이러한 방법으로 아래 그림과 같이 문자열이 끝날 때 까지 반복합니다.

 

 

구획 문자 위치 지정 방법

 

이를 아래와 같이 구현할 수 있습니다.

 

void parse(const string& str, vector<string>& values, string& delimiter)
{
    // str: 전체 문자열
    // values: sub string을 저장할 벡터
    // delimiter: 파싱 기준 구획 문자
    string::size_type Fpos = str.find_first_not_of(delimiter, 0);
    string::size_type Lpos = str.find_first_of(delimiter, Fpos);

    while (string::npos != Fpos || string::npos != Lpos)
    {
        values.push_back(str.substr(Fpos, Lpos - Fpos));
        Fpos = str.find_first_not_of(delimiter, Lpos);
        Lpos = str.find_first_of(delimiter, Fpos);
    }
}

 

앞서 언급한 바와 같이 전체 문자열이 끝날 때까지 Fpos와 Lpos를 구하고 substring을 추출하는 것을 반복합니다. substr을 통해 파싱할 때 Fpos와 Lpos-Fpos 사이의 값을 추출해서 벡터에 저장해주기만 하면 됩니다.

 

 

문자열을 제거해 나가며 파싱하는 방식

 

이 방법은 구획문자의 위치만 찾으면 되는 방법입니다. 간단히 말하면 추출한 sub string을 원본 string에서 제거하고 탐지해 나가는 방법입니다. 따라서 앞서 언급한 포지션 지정 방식과는 다르게 아래 그림과 같이 sub string을 탐색할때의 시작 지점은 무조건 0 입니다.

 

구획문자 지정 방법

 

이를 코드로 구현하면 다음과 같습니다.

 

void parse(string str, vector<string>& values, string& delimiter)
{
    // str: 전체 문자열
    // values: sub string을 저장할 벡터
    // delimiter: 파싱 기준 구획 문자
    
    int pos = 0;
    string token;
    
    while ((pos = str.find(delimiter)) != string::npos)
    {
        token = str.substr(0, pos);
        values.push_back(token);
        str.erase(0, pos + delimiter.length());
    }
    
    values.push_back(str); 
}

 

여기에서 주의해야 할 점이 몇 가지 있습니다.

 

1. 원본 string이 바뀐다는 점을 주의하기 바랍니다. 앞서 언급한 포지션 지정 방식과 다르게 문자열 제거 방식은 sub string을 원본 string에서 제거함으로써 시작 지점을 계속 0으로 만든다는 것이 포인트입니다. 이 말인즉슨, 원본 string을 유지해야 하는 경우에는 불가피하게 따로 string 변수를 복사해서 사용해야 함을 의미합니다. 따라서 코드에서 보시는 바와 같이 파라미터로 넘길 때 원본 문자열(str)의 const도 제거하고 참조연산자(&)도 제거하였습니다.

 

 

2. 마지막 substring은 따로 파싱할 수 없습니다. 왜냐하면 위의 코드 구조상 substring의 마지막에 구획 문자가 있는 경우에만 substring을 저장할 수 있는데, 원본 string에 마지막 character에 구획문자가 없으면 파싱을 안하고 끝내기 때문입니다. 즉, "Welcome to my blog."에서 "blog." 만 파싱하지 못하고 while루프를 종료하게 되죠. 그래서 마지막으로 남겨진 문자열을 추가하기 위해 values.push_back(str)을 통해 원본에 남은 문자열을 넣어주는 것입니다. 물론 원본 문자열 마지막에 구획문자가 있으면 while문을 통해 전부 파싱할 수 있습니다.

 

앞서 언급한 포지션 지정 방식과 문자열 제거 방식은 아래와 같이 main에서 함수를 호출함으로써 결과를 확인할 수 있습니다.

 

#include <string>
#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream>

using namespace std;

int main()
{
    vector<string> values;
    string delimiter(" ");
    string str("Welcome to my blog.");

    parse(str, values, delimiter);

    for(auto& value : values)
        cout << value << endl;
    
    return 0;
}

 

결과:

 

Welcome                                                                                                               
to                                                                                                                    
my                                                                                                                    
blog.

 

Boost Tokenizer를 사용하는 방법

 

 서문에서 언급한 바와 같이 자바에서는 자체적으로 문자열 파싱을 위한 Tokenizer 기능을 제공합니다. C++의 경우 STL 라이브러리를 통해 제공되고 있지는 않지만, Boost 라이브러리를 활용하면 Toknizer를 사용할 수 있습니다. 기능도 앞서 예시로 보였던 예제에서 확장하여 아래 코드와 같이 다수의 구획문자를 동시에 검사할 수 있습니다. Boost 라이브러리를 사용할 수 있는 환경인 경우에는 적극 추천합니다.

 

#include <boost/tokenizer.hpp>
#include <string>
#include <iostream>
#include <vector>
 
using namespace std;
using namespace boost;

void parse(const string& str, const string& delimiters)
{
    char_separator<char> sep(delimiters.c_str());
    tokenizer<char_separator<char> > tok(str, sep);
    
    for (tokenizer<char_separator<char>>::iterator i = tok.begin(); i != tok.end(); ++i)
        cout << *i << endl;
}

int main()
{
    string delimiters=" :./";
    string str("current post url:https://itguava.tistory.com/55");

    parse(str, delimiters);
        
    return 0;
}

 

- delimiters: 파싱 기준으로 적용하기 위한 모든 구획문자를 지정합니다.

- char_separator<char>: 전체 문자열에서 구획문자별로 쪼개는 역할을 담당하는 클래스입니다.

- tokenizer<char_separator<char>>: 실제로 토큰으로 쪼개진 결과를 컨테이너 뷰로 제공합니다.

 

결과:

 

current
post
url
https
itguava
tistory
com
55

 

(본 toknizer를 활용하는 방법은 Boost 1.59.0, Gcc4.4.7, C++0x(GNU) 컴파일 환경에서 테스트하였습니다.)

 

이 밖에도 C함수인 strtok()를 활용하거나, 다른 다양한 방법들이 있습니다. 위의 세 가지 내용은 제가 주로 사용하는 방법을 중심으로 공유한 내용이니 많은 참고 바랍니다.