#015_자료구조와 알고리즘_수식 트리

안녕하세요 삽잡이입니다.

이번 시간에는 수식 트리에 대해서 알아보려고 합니다.

우선 이번 내용에는 절대적으로 코드는 없습니다... 

그냥 어떻게 해야할지 정리해보는 시간이기 때문이죠... 허허... 

아무튼, 시작해보도록 하겠습니다.

만약에 수식 인자를 받아서 계산하는 프로그램을 만들어본다고 하지요.

4+2*3-9/2 이렇게 말입니다...

그렇다면 계산의 순서는 어떻게 진행될까요? 왼쪽부터 차례대로? 푸하하... 

그렇게하면 안된다는건 너무도 당연하게 아시리라 믿습니다...

자... 그럼 우리는 어떻게 계산을 하게 해야할까요?

우선 연산자 우선순위에 의해서 곱하기 및 나누기를 우선적으로 연산해줘야 하는데요,

간단하게 stack을 사용하여 우리는 이 문제를 해결할 수 있게 됩니다.

스택은 순차적으로 값을 저장하고 맨 마지막부터 값이 빠져나가는

FILO (First In Last Out) 방식을 사용하고 있는 저장소입니다.

방식은 이렇습니다... 

피연산자는 스택에 집어넣고 연산자를 만나게 되면 피연산자 두개를 꺼내옵니다.

꺼내온 두개의 피연산자를 연산자를 통해 계산을 하고 다시 그 결과를 스택에 집어 넣게 되는 것이지요.

이를 식이 끝날 때까지 반복하게 된다면 문제를 해결할 수 있습니다.

하지만 여기서는 에러사항이 있습니다.

바로 계산을 할 식을 후위 표기에 의해 표현해야한다는 것이지요.

맨 처음 계산은 중위 표기법에 의해 표현된 식인데요, 그 표현을

4 2 3 * 9 / + 2 -

이와 같이 표현해야한다는 것입니다... 이를 어찌 표현합니까...

그래서 우리는 기존에 사용하는 중위 표기식으로 이루어진 식을 

후위 표기로 변환하는 방법을 사용하면 됩니다.

음... 어떻게 할까요?

우선, 식을 한 문자씩 받아온 뒤에 만약 받아온 문자가 피 연산자이면 후위 표기식에 적습니다.

만약 받아온 문자가 연산자이면 스택에 집어넣는 것이지요...

여기서 좀 복잡한 것이,

왼쪽 괄호가 온다면 stack에 보관해두고 출력을 계속해서 진행합니다.

그러다가 연산자가 나오면 stack에 또 보관을 합니다. 

오른쪽 괄호를 만나게 된다면 stack에 보관되있던 

연산자를 후위 수식에 의해 연산을 진행하면 되는 것이지요.

괄호가 없다면 연산자만을 stack에 삽입하고...

... 기존 후위 수식 연산과 똑같이 진행하면 됩니다.

으아아아 정신이 없어 잘 안풀린다... 혹시나 이 글을 읽고 계신 분들이 있다면

'중위 후위 표기 변환'이라고 검색해보신다면 도움이 되실 것입니다.

글이 산으로 가고있다.... 흐허허...

아무튼,

중위 수식을 후위 수식으로 변환시켜 계산할 수 있는 방법도 있었지만...

또 다른 방법이 있습니다. 뭐 물론 방법은 많이 있겠지요...

제가 언급하는 방법은 뭐냐 하면 바로 수식 트리를 사용하는 것입니다.

수식 파서 트리라고도 할 수 있는데요, 우선 파서가 뭐냐 하실 수 있으니...

우선, 원본 데이터를 가공해서 우리가 원하는 결과물로 변환시켜가는 일련의 과정을 파싱이라고 하는데요

이와 같은 행동을 해주는 친구를 파서라고 하지요...

그건 그렇고... 아무튼, 

그렇다면 수식 트리를 만들려면 어떻게 해야할까요?

그전에 이미 언급했어야했지만, 수식이란 무엇일까요?

'연산자와 피연산자의 조합이요!' 

예... 반은 맞고 반은 틀린... 답입니다. 

왜냐하면, 연산자와 피연산자의 조합이 무조건 수식은 아니기 때문입니다.

수식이라고 말하기 위해서는 특정한 규칙이 성립되어야 합니다.

우선, 수식이란 우리가 계산할 수 있는 식이라고 정의할 수 있는데요,

연산자는 없을 수도 있지만 여러번 반복할 수 있다는 조건을 가지고 있습니다.

뭐 당연한 말일 수도....

그리고, 연산자와 피연산자 쌍이 반복해서 올 수 있습니다.

피연산자는 최소 하나가 오거나 여러개 반복해서 올 수 있지요..

이런걸 왜 말하느냐 하면, 어떠한 문법을 정규식으로 표현했을 때 반복적임을 나타내면

파서 트리로 나타낼 수 있기 떄문입니다.

위의 설명을 정규식으로 나타내게 된다면,

<experience> := <피연산자><mid_experience>0 으로 나타낼 수 있습니다. 

(위의 정규식에서 0은 안올 수 도 있지만 여러번 반복할 수 있다는 말입니다.)

추가적으로 

<mid_experience> := <연산자><피연산자>

<연산자> := <+> | <-> | <*> | </>

<피연산자> := <digit>* 

(위의 식에서 +로 대체할 수 있는데, 

이와 같이 표현하는 것은 최소 하나가 오거나 여러개 반복해서 올 수 있다는 뜻입니다.)

<digit> := <1> | <2> | <3> | <4> | <5> | <6> | <7> | <8> | <9> | <0>

이와 같은 정규식들을 통해 

수식 트리를 통한 계산 코드를 구현할 수 있게 됩니다.

우선 계산하기 위한 절차는 컴파일러가 하는 기본 절차 원리와 비슷합니다.

자... 컴파일러가 한번 되보도록 합시다.

1. Lexical (어휘 분석 (토큰 생성) 을 한다.)

즉, 42+3*9-1/423 이렇게 입력을 했다고 치면, 우리가 입력한 원본 데이터 중에서 문법에 맞지 않는

토큰들이 있는지 확인하고 그러한 부분들이 있다면 error를 던지는 것입니다.

그렇지 않다면, 각각 토큰의 위치를 생성해주는 작업을 진행하는 것입니다.

즉, 의미있는 최소 단위로 묶는 작업을 Lexical 작업에서 진행하는 것이지요.

참고로, Lexical 작업에서 에러가 나면 그 자체에서 에러를 던지고 끝내기 때문에 

이부분에서 에러를 해결했지만 오히려 더 많은 에러가 생성될 수 있습니다. 

다음 부분들에서 에러가 있다면 말이지요...

2. Syntax (문법 체크를 한다.)

말 그대로 문법에 맞는지 틀린지를 체크합니다.

3. Semantic (형식 체크)

문자열을 대입해야하는데 정수값이 온다던지, 정수값을 대입해야하는데 문자열이 온다던지...

우리가 데이터를 보관할 수 있는 형식과 실제 보관된 형식이 다르다고 하면 형식 미스 매치가 발생합니다.

언어에서 형식 미스 매치가 발생하게 되었을 때, 

자체적으로 변환을 해준다면 이를 '묵시적 형변환' 이라 부르고

개발자가 명시를 하여 변환 해준다면 이를 '명시적 형변환'이라고 부릅니다.

형식 체크를 할 경우 경고에 그치는 경우도 있고, error를 던저주는 경우도 있습니다.

혹은, 묵시적 형변환이 되어 컴포팅 되는 경우도 있습니다.

4. Parsing 가공

고급 언어로 되어있는 것들은 기계어로 변환되는 과정을 반드시 거칩니다.

원본 데이터를 목적 데이터로 변환 시키는 과정 (컨버팅)을 파싱이라고 합니다.

5. Code Generation

파서를 통해 가공된 목적 데이터를 가지고 코드를 생산하는 과정입니다.

파싱을 하기 위해서 어떠한 자료구조를 쓰냐에 따라 파서가 달라지는데,

위와 같은 컴파일 과정 처럼 수식 트리를 통한 계산기를 만들 수 있습니다.

물론, 이번시간에는 만들지는 않습니다... 하하...

오늘은 정말 쓸대 없이 구구절절 이상한 소리만 내뱉은거 같습니다....

글도 정리가 잘 안되는 거 같구...

여름 끝물이 가니 체력도 끝물로 가는 듯한...

아무튼, 오늘 굳이 건저갈 수 있는 내용이라면...

음... 파싱을 하기 위해서는 정규식을 만들고 정규식에 맞게 끔 코딩해야한다?

허허... 정규화 하는게 말처럼 쉬운지...

제가봐도 스스로가 이상하군요....

다음시간에 뵙겠습니다.

삽잡이였습니다~!