Expression Parser in Java #1

우연히

C/C++로 데이터마이닝 툴 만들다가 적(跡)이 바뀌는 바람에 Java로 작업을 하고 있다. 12~3년 전에 잠깐 써보고 다시 하는 건데 아쉬운 부분도 있지만, 신경 쓸 부분이 많이 줄어 꽤 편하게 작업하고 있다. 하지만 어떤 클래스가 무슨 기능을 하고 어떤 메소드를 이용해야 하는 지 잘 모르니 많이 뒤져 보면서 필요한 것들을 찾고 있다.

그러던 중, Shunting-Yard Algorithm을 우연히 알게 되었다. 예전에 C/C++로 수식파서 만든다고 있는 머리 없는 머리 굴려가며 고생한 적이 있었는데 그때 이걸 알았다면 많이 쉽게 하지 않았을까 싶다. 수식파싱할 때 어려운 게 연산의 순서를 계산하는 것인데 이 알고리즘을 이용하면 쉽게 할 수 있기 때문이다.

데이터를 가공 / 처리할 때 수식을 통하여 새로운 의미의 변수를 만드는 작업을 굉장히 많이 한다. 이런 파생변수를 만들 때 필요한 것이 수식파싱 후 값을 계산하는 모듈이다. 공부도 할 겸 Java로도 이 모듈을 만들어 놓으면 여기 저기 쓸 데가 있지 않을까 싶다.

잠깐만 시간을~

그렇다면, 날 다시 수식 파싱의 세계로 밀어 넣은 Shunting-Yard Algorithm은 뭔지 잠깐만 시간을 내 보자.

출처: Wikipedia

1에 2를 더하는 수식을 우리는 보통 "1 + 2"로 표시한다. 이와 같이, 보통 우리가 쓰는 수식은 infix notation 방식을 취하고 있다. 무슨 말인고 하니 연산자가 가운데(in) 있다는 얘기다.

Shunting-Yard Algorithm은 infix notation 형태의 수식을 Reverse Polish Notation (RPN) 형태로 바꾸는 데 사용할 수 있는 알고리즘이다. RPN은 연산자를 뒤에 위치시키는 표현법으로 "1 + 2"를 "1 2 +"와 같이 표시한다.

사람이 보기에는 "1 더하기 2"나 "1과 2를 더해"나 별 차이 없어 보이지만 컴퓨터가 보기엔 천지차이다. RPN 형태로 되어 있으면 루프 돌면서 쭉 계산해 나가면 되는데 infix 형태로는 그렇게 하기가 힘들다. 그래서 RPN 형태로 변경해야 하고 Shunting-Yard와 같은 알고리즘을 이용하는 것이다.

Shunting-Yard Algorithm은 이름에서 알 수 있듯이 차량기지(Shunting yard)에서 기차를들 정렬하기 위하여 사용하는 방식과 비슷하게 로직이 수행된다. 자세한 내용은 Wikipedia 참고.

Pseudocode

이야기를 풀어 나가기 위하여 Shunting-Yard Algorithm의 처리 과정을 정리해 보았다.

for each token in expression
{
    if token == 'number'
        token --> output queue

    if token == 'function'
        token --> stack

    if token == 'function argument separator' (e.g. a comma)
    {
        while( stack not empty and top of stack != '(' )
            pop stack onto output queue
        if top of stack != '('
            mismatched parentheses error.
        else
            pop '(' off stack, ignore it.
    }

    if token == 'operator'
    {
        while( stack not empty and stack top token == 'operator' )
        {
            if token precedence < stack top token or (token == left-associative and precedence <= stack top token)
                pop stack onto output queue
            else
                break
        }
        token --> stack
    }

    if token == '('
        token --> stack

    if token == ')'
    {
        while( stack not empty and stack top token != '(' )
            pop stack onto output queue
        if stack is empty
            mismatched parentheses error.
        pop '(' off stack, ignore it.

        if top of stack == 'function'
            pop stack onto output queue
    }
}

while( stack not empty )
    pop stack onto ouput queue

만들어 보자

알고리즘만 간단히 구현할 거라면 필요 없겠지만, 확장성 있는 수식파서를 만들기 위해 Psedocode를 보면서 우리가 알 수 있는 것들을 정리해 보자.

1. 우선, 수식을 한땀 한땀 이태리 장인처럼 따서 Token을 추출할 무언가가 필요하다.
2. 추출된 Token에 따라 처리할 내용이 달라지는 것을 보아 Token은 특정 형태를 가지고 있다.
3. 형태는 수식에 사용되는 연산자(Operator), 숫자(Operand), 함수(Function)와 괄호, 쉼표 등이 있다.
4. 연산자는 left-associative, right-associative의 형태를 가진다.
5. 알고리즘을 구현하기 위하여 Stack 한개와 Queue 한개가 필요하며,
6. 수행완료 후 결과는 Queue가 남는다.
7. 수식을 계산을 위한 것이므로 이 Queue에는 계산 순서에 맞게 Token이 위치할 것이다.
8. Queue와 Stack에는 Token이 들어 간다. 다양한 Token을 넣기 위한 인터페이스가 필요하다.
9. 수행 중 괄호가 맞지 않는 경우 등 사용자 오류를 처리하기 윈한 Exception 클래스가 필요하다.

정리된 내용을 수용하려면 다음과 같은 것들을 만들어야 할 것 같다.

만들 애 이름	기능/역할	비고
ExprParser	수식파서 메인 클래스	-
ExprTokenizer	수식을 잘 잘라서 Token을 뽑아 줄 클래스	1번
ExprTokenType	Token의 형태를 정의한 Enumeration. 연산자, 괄호, 함수, 피연산자 등을 정의.	2번, 3번
OperatorAssoc	연산자의 Associative 방법을 정의한 Enumeration	4번
ExprToken	ExprTokenizer에서 Token을 이 객체로 추출	2번, 8번
OperatorToken	연산자를 처리하기 위한 토큰	3번
FunctionToken	함수를 위한 토큰	3번
ValueToken	피연산자를 대변하기 위한 토큰	3번
EtcToken	연산자, 함수, 피연산자 이외 것을 대변하기 위한 토큰. 예를 들어 괄호 같은 거~	3번
ParserException	수식파싱 및 값 계산 중 발생할 수 있는 오류 처리 클래스	9번

5번에서 필요한 Stack과 Queue는 알고리즘 구현할 때 java.util 패키지에 있는 것을 이용하면 된다. 6번은 파싱하는 메소드에서 생성한 Queue를 반환하거나 멤버 변수로 저장하면 되고, 7번은 알고리즘의 결과이다.

조금만 더 생각해 보자.

수식 내에서 Token을 구분짓는 건 Token의 형태를 문자로 표현한 것들이다. 무슨 말인고 하니, 연산자, 숫자, 괄호, 함수 등을 표현한 수식 내 문자들이 Token을 뽑는 기준이라는 것이다. 오호라~ Token 뽑는 방법은 수식내 문자를 하나 하나 살펴보며 앞서 말한 문자와 일치하는 지 비교해 보면 될 듯 하다.

그렇다면 어떤 문자들이 있을까? 연산자를 먼저 살펴보면, 사칙연산(+, -, *, /)을 기본으로 승수연산(^), 나머지 연산(Modulus, %) 등이 있다. 물론, 비교 연산자(=, >=, <=, !=), 논리 연산자(and, or, not)도 포함되면 좋을 것이다. 숫자와 괄호는 특별히 말할 것이 없고, 함수는 정의하기에 따라 무궁무진 하기 때문에 연산자처럼 몇 개 정의해서 끝날 문제가 아니다. 뭔가 함수객체 들만 몰아 넣어 관리할 Gallery스러운 것이 필요하다. 조금 더 나가서 연산자도 함수처럼 관리하면 편할 것 같다. 실제 계산하는 메소드도 같이 포함시켜 놓고~

그래서 다음과 같은 것들을 추가로 만들면 조금 더 멋진 파서가 되지 않을까 싶다.

만들 애 이름	기능/역할
ExprTokenGallery	연산자, 함수 형태의 Token을 자신을 표현할 문자와 함께 Key & Value 형태로 관리하는 클래스.
Calculatable	연산자나 함수의 실제 계산을 위한 인터페이스. Token을 정의한 클래스에 멤버로 넣어 쉽게 값을 계산할 수 있게 함.

다음 편에 계속

휴... 사실 이 글을 쓰기 시작한 지 한달이 넘었다. 살은 더 붙여야 하지만 위에서 말한대로 구현도 다 해놨다. 그런데 왜 이리 안써지는지... 일 때문에 바쁜 것도 있었지만 이렇게 안써질 때가 가끔(사실 아주 많이) 있다. 이럴 땐 잠시 시간을 가져야 한다. 여기서 잠시 멈추고 다음에 소스와 함께 다시 해야겠다.