우연히
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를 보면서 우리가 알 수 있는 것들을 정리해 보자.
- 우선, 수식을 한땀 한땀 이태리 장인처럼 따서 Token을 추출할 무언가가 필요하다.
- 추출된 Token에 따라 처리할 내용이 달라지는 것을 보아 Token은 특정 형태를 가지고 있다.
- 형태는 수식에 사용되는 연산자(Operator), 숫자(Operand), 함수(Function)와 괄호, 쉼표 등이 있다.
- 연산자는 left-associative, right-associative의 형태를 가진다.
- 알고리즘을 구현하기 위하여 Stack 한개와 Queue 한개가 필요하며,
- 수행완료 후 결과는 Queue가 남는다.
- 수식을 계산을 위한 것이므로 이 Queue에는 계산 순서에 맞게 Token이 위치할 것이다.
- Queue와 Stack에는 Token이 들어 간다. 다양한 Token을 넣기 위한 인터페이스가 필요하다.
- 수행 중 괄호가 맞지 않는 경우 등 사용자 오류를 처리하기 윈한 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을 정의한 클래스에 멤버로 넣어 쉽게 값을 계산할 수 있게 함. |
다음 편에 계속
휴... 사실 이 글을 쓰기 시작한 지 한달이 넘었다. 살은 더 붙여야 하지만 위에서 말한대로 구현도 다 해놨다.
그런데 왜 이리 안써지는지... 일 때문에 바쁜 것도 있었지만 이렇게 안써질 때가 가끔(사실 아주 많이) 있다.
이럴 땐 잠시 시간을 가져야 한다. 여기서 잠시 멈추고 다음에 소스와 함께 다시 해야겠다.
