크리스마스는 그동안 미루어왔던 코딩을 하는 시간이다. 산타할아버지가 특별히 공부를 하시라고 주신 선물이 분명하다.

-------------------------------------------

그 기념으로 강좌를 하나 가져왔습니다.

공부합시다. 오늘은 크리스마스입니다.

-------------------------------------------

수식분석하기


수식을 중간언어로 변환하기 위해선 후위표기법의 아이디어가 필요합니다.(꼭 트리구조에 맞추어 만들 필요는 없습니다.)
다만, 수식을 이용해 값을 구하는 목적이라면 후위표기법과 같은 복잡한 방법은 필요없을 듯 보입니다.

실제로 수식이 이용되는 대부분의 목적은 중간언어로 표현하는 것이 아닌 단순히 값을 구하는 경우이기 때문에 위의 복잡한 방법말고 아래(다만,)을 하는 방법을 알아보고자 합니다.

C언어를 공부하면서 연산자 우선순위에 대해 한 번 씩은 들어보셨을 겁니다.
증감연산을 포함한 몇 가지 연산자를 빼면
1순위: *, /
2순위: +, -
3순위: %
4순위: <<, >>
5순위: <=, >=, <, >, ==, !=
6순위: &, ^, |
7순위: &&, ||
로 나타낼 수 있습니다. 생략된게 하나있다면 괄호연산이겠네요.
괄호연산은 가장 먼저 처리된다는 것을 아마 알 것입니다.

간단한 수식을 예로 들어볼게요.
가령, (3 + x) * (1 - y)라는 식은
'3+x를 수행하고, 1-y를 수행한 뒤 각각의 결과값을 *연산하라'라고 해석할 수 있습니다.
*연산은 C언어에선 곱셈이나 포인터 연산이지만, 여기선 곱셈만 다룬다고 약속합시다.

그럼 위 수식을 우리는 어떻게 분석했을까요?
전체를 부분으로 쪼개어 나타내면 쉽게알 수 있을 것 같습니다.
전체를 보면 (~~~) * (~~~)와 같이 곱셈이 중간에 박혀있는 구조로 되어있네요
각 괄호를 X, Y라고 한다면 X * Y라는 연산이 되겠네요.
그럼 괄호들을 X, Y라고 치환했으니 이제 X와 Y의 값을 구하면 될겁니다.
X는 3 + x이고, Y는 1 - y이니 x와 y값을 대입하면 원하는 값을 얻을 수 있죠.

위 식이 단순한 이유 중 하나는 각 연산자가 양 옆으로 두 개의 값을 가지고 다른 우선순위를 볼 필요없이 연산할 수 있다는 곳에 있습니다. 그러면 이것저것이 뒤죽박죽 섞인 수식은 어떻게 분석해야될까요?

그런 식의 예로 다음과 같은 식을 분석해 봅시다.
x + y - z * 2 + k * (x - y)
위 수식에서 가장 먼저 연산될 수 있는 것은 가장 높은 우선순위를 가진 (x - y)이나 이것은 사람이 볼 때나이지 컴퓨터로 저 괄호가 저기에 있어 먼저 처리해야된다는 논리로 접근을 시도하면 무척 어려운 접근법이 될것입니다.
그럼 제대로 분석해보죠

컴퓨터의 입장에서 볼땐 가장 먼저 처리되는 것은 x + y라는 식입니다.
바로 뒤에 +연산자 보다 높은 우선순위를 가진 연산자가 없으므로 먼저처리 할 수 있죠.
x + y의 연산된 값을 t1이라는 변수에 넣어서 식을 표현하면
t1 - z * 2 + k * (x - y)와 같이 표현가능 합니다.
포인터를 다음 연산자로 옮겨보죠
다음에 만난 것은 -연산자 입니다. 대충 위에서 설명한 내용대로라면 t1 - (~~~)라는 식으로 표현할 수 있죠.
그러니 해당 식을 분석하기 위해선 (~~~)의 정보를 알아야합니다. 정보는 우선순위에 관한 정보나 값의 정보 정도가 될 수 있곘네요. 일단 보류 해두고 (~~~)영역을 분석하러 갑시다.

(~~~)영역에서 첫 번째로 만난 연산자는 *연산자 입니다. 이는 -연산자 보다 높은 우선순위를 가진 연산자로 -보다 먼저 처리되어야하죠. 그러므로 t1 - (~~~)에서 -연산보다 (~~~)의 일부가 먼저 처리되어야합니다.
위의 내용들을 종합하여 보면 t1다음으로 처리될 부분은 z * 2의 부분입니다. 이를 t2로 치환해보면
t1 - t2 + k * (x - y)로 나타낼 수 있습니다. 이제 대충 아실듯하니 뒷 부분은 분석하지 않겠습니다.

최종적으로 k * (x - y)까지 t3로 치환하면, t1 - t2 + t3라는 식이 나타납니다.
이 식은 수학 연산에서 우선순위가 동등한 연산규칙에 의해 (t1 - t2) + t3로 나타낼 수 있고, 해당 식에 x, y, z, k값을 넣어주면 분석이 가능합니다.

따라서 분석하려는 x + y - z * 2 + k * (x - y)라는 식은 연산자 우선순위 규칙에 의해
((x + y) - (x * 2)) + (k * (x - y))
로 나타낼 수 있습니다. 이 식은 (3 + x) * (1 - y)와 같이 식만 조금 복잡할 뿐이지 각각 (~~) <연산자> (~~)형태로 나타나 있어 쉽게 연산이 가능합니다.

이제 약간 복잡한 방법으로 위 방법들을 일반화 시켜보겠습니다.
모든 수식의 부분들은 (~~) <연산자> (~~)형태로 나타나 있습니다. 이것을 var이라고 하겠습니다.
이 식에서 정해지지 않은 영역 (~~)은 factor라고 하겠습니다.

그러면 var = factor <연산자> factor 로군요
factor라는 것에는 괄호가 올 수도 있고, 숫자가 올 수도 있고, 변수가 올 수도 있습니다. 이와 더불어 (var)도 올 수 있죠.
마지막에 (var)이 온다는 말은 잘 이해가 안될 수 있습니다만, 간단하게 생각하면 됩니다. 위에서 지 멋대로 나타나 있는 수식을 괄호로 씌우면 간단해졌죠? 그와 같이 factor라는 부분에 (var)도 올 수 있다는 말입니다. 
또한 var은 (~~) <연산자> (~~)라고 표현하였지만 수식에선 숫자 하나나 문자 하나와 같이 나타나 있는 경우도 있습니다. x = 1 이라는 수식에서는 =의 오른쪽에 있는 1이 var영역이지만 숫자하나면 덩그러니 와있네요. 그래서 var에도 숫자, 변수가 올 수 있이니 최종적으로 factor도 올 수 있겠군요.

위 문장 전체를 기호로 표현하면
var = factor <연산자> factor
      = factor
factor = 숫자
          = 변수
          = ( var )
이 됩니다.

위 일반화된 표현식을 가지고 ((x + y) - (x * 2)) + (k * (x - y))를 분석해볼게요.
가장 먼저 보이는 것은 var = (factor) + (factor) 부분 이네요. 각각의 factor는 (x + y) - (x * 2)와 k * (x - y)를 가리킵니다.
한 번더 들어가면 (x + y) - (x * 2) 식은 또 (factor) + (factor)로 되어있네요. 더 깊이 들어가면 factor + factor = x + y = 변수 + 변수로 되어있습니다. 변수는 factor니 factor로 표현할 수 있겠죠. 따라서 위 식은 다음과 같은 방법으로 변하게 됩니다.

var = ((변수 + 변수) - (변수 * 숫자)) + (변수 * (변수 - 변수))
하지만 그냥 문자는 변수로 숫자는 숫자로만 나타낸 것 뿐이지 뭐가 달라졌는지 모르겠습니다. 다만, 이런 식으로 나타내면 어떨까요?

var1 = x + y
var2 = x * 2
var3 = var1 - var2
var4 = x - y
var5 = k * var4
var6 = var3 + var5
하지만 이건 factor가 보이지 않는 군요. 더 자세히 나타내 봅시다.

factor1 = x
factor2 = y
var1 = factor1 + factor2
factor3 = 2
var2 = factor1 * factor3
var3 = (var1) - (var2)
var4 = factor1 - factor2
factor4 = k
var5 = factor4 * (var4)
var6 = (var3) + (var5)
이제 위에서 문장전체를 기호로 표현한 부분과 대조하여 보면 거의 비슷해졌군요. 하지만 (var1)도 factor가 되니 최종적으로는

factor1 = x
factor2 = y
var1 = factor1 + factor2
factor3 = 2
var2 = factor1 * factor3
factor4 = (var1)
factor5 = (var2)
var3 = factor4 - factor5
var4 = factor1 - factor2
factor6 = k
factor7 = (var4)
var5 = factor6 * factor7
factor8 = (var3)
factor9 = (var5)
var6 = factor8 + factor9
와 같이 나타낼 수 있습니다. 위식이 너무 길고 더럽게 느낄 수 있지만, 컴퓨터는 저 한 줄 한 줄을 모두 한 번 이상은 변수에 담아서 연산하게 됩니다. 물론 사람이 저런식으로 해야된다는 건 아니니깐 저런 무식한 방법으로 나타낼 필요는 없습니다.

그럼 이렇게 나타낸 연산은 어떻게 할까요?
별로 어렵지 않습니다.
그냥 저걸 그대로 연산시키면 됩니다. 어려운 부분은 없어요.

그냥 함수를 몇개 만들어 재귀호출 시켜버리면 쉽게 만들 수 있습니다.
식을 입력하는 함수를 var이라고하고 나머지 찌끄레기들을 처리하는 함수를 factor라고 한다면 이 두 함수로 나누어 작업하면 쉽게 가능합니다.
아, 한 가지 염두하지 못한게 있네요. 연산자 우선순위에 관한 문제입니만, 이건 단순히 다단계로 함수를 호출함으로 써 구현할 수 있습니다.
+, -, *, /만 가지고 다단계로 나누어 보면
factor1 = factor2 + factor2
            = factor2 - factor2
factor2 = factor * factor
            = factor / factor
로 연산자 우선순위 문제를 해결할 수 있습니다. 이해가 안되시면 저기 위에 문장전체를 기호로 표시한 것과 같이 식을 분석해 보세요. 쉽게하실수 있을 겁니다.

이제 모든 준비는 끝났으니 C언어로 구현해봅시다.

C언어에는 클래스가 없으니 정적변수로 하여금 포인터를 조작하는 방식으로 연산하겠습니다. 함수는 여러개지만, 계속 주거니 받거니 하면서 포인터를 바꾸어 연산하는 것은 별로 정신건강에 좋지 않을 것 같거든요.
먼저 main 부분입니다.


static const char *pointer; static int x, y, k; int main() { int result; const char *sic = "((x+y)-(x*2))+(k*(x-y))"; x = 0, y = 0, k = 0; pointer = sic; result = var(); printf("%d", result); }


매우 간단합니다. 저기 있는 x, y, k 변수에 적당한 값을 넣어주면 var함수가 원하는 대로 식을 계산해줄 것입니다.

그럼 var함수를 만들어 보겠습니다.
var함수는 factor, factor <연산자> factor구문을 분석하므로, factor를 호출함을 알 수 있습니다.
하지만 이렇게만 연산하도록 시키는 건 우선순위에 관한 문제를 처리하기란 너무 어려운 문제이고, var함수는 factor1함수만 호출하면 되는 매우 간단한 구조이므로 var함수는 +, -연산을 처리하는 부분이 포함되게 다음과 같이 제작합니다.

int var()
{
    int result = factor2();
    while((*pointer == '+') || (*pointer == '-'))
        if(*pointer == '+') 
        {
            pointer++;
            result += factor2();
        }
        else if(*pointer == '-')
        {
            pointer++;
            result -= factor2(); 
        }
    return result;
}

반복문이 있어 뭔가 어려운 구조이지만 + ~~ - ~~ + ~~ ...로 나열된 부분이라면 어차피 처리할 꺼 다시 var을 호출해서 하는 것보단 나아보이므로 그렇게 처리하였습니다.

var이 저런 식이면 factor 2함수는 거의 동등한 모양이겠네요.



int factor2()
{
    int result = factor();
    while(*pointer == '*' || *pointer == '/')
        switch(*pointer)
        {
        case '*':
            pointer++;
            result *= factor();
            break;
        case '/':
            pointer++;
            result /= factor();
            break;
        }
    return result;
}


마지막으로 factor함수를 만들면 됩니다.
factor함수는 숫자, 변수, (var)을 처리하면 되므로 다음과 같은 식이 만들어 지겠네요.


int factor()
{
    int result = 0;
    if (*pointer == '(')
    {
        pointer++;
        result = var();
        if (*pointer == ')')
        {
            pointer++;
            return result;
        }
    }
    else if(('0' <= *pointer) && (*pointer<= '9'))
    {
        while(true)
            if('0' <= *pointer&& *pointer<= '9') 
            {
                result *= 10;
                result += *pointer - '0';
                pointer++;
            }
            else
                break;
        return result;
    }
    else if(*pointer== 'x') 
    {
        pointer++;
        return x;
    }
    else if(*pointer== 'y') 
    {
        pointer++;
        return y;
    }
    else if(*pointer== 'k') 
    {
        pointer++;
        return k;
    }
}


숫자를 전부 가져오는 구문 덕분에 식이 약간 길어졌습니다만, 쉽게 이해할 수 있습니다.

다음 게시글에서 ...