중위 표기식 트리 구조 생성 알고리즘

이미 이런 알고리즘이 존재 하는지는 모르겠지만, ( 있지만 내가 못찾은거라고 생각한다. 사실 찾기가 귀찮았다. ) 혼자서 만들어본 알고리즘을 내가 나중에 봐도 이해할 수 있도록 블로그에 포스팅 해 보고자 한다. 먼저 연산자들의 우선순위를 정하자면 다음과 같다.

연산자	우선 순위 (클수록 높음)
접근자 (.)	5
비트 연산자 (&, |, <<, >>)	4
곱셈 / 나눗셈 (*, /)	3
덧셈 / 뺄셈 (+, -)	2
비교 연산자 (==, >, >=, <, <=)	1
논리 연산자 (&&, ||)	0

접근자는 C 언어 또는 JAVA에서 car.drive(); 처럼 하위 맴버에 접근할 때 쓰는 기호를 이야기 한다. 정확히 뭐라고 지칭하는지 몰라서 접근자라고 했다.

우선 순위를 쉽게 설명하자면, 우선 순위가 낮을 수록 제일 나중에 묶여도 되고 높을 수록 제일 먼저 묶여야 한다는 것을 의미한다.

예를 들어 다음과 같은 표현식이 있다고 하자.

a + b * c + d

곱셈은 덧셈보다 우선순위가 높으므로 곱셈을 먼저 묵는다.

a + ( b * c ) + d

이제 a 다음에 있는 덧셈을 묶는다.

( a + ( b * c ) ) + d

마지막 남은 덧셈을 묶는다.

( ( a + ( b * c ) ) + d )

분석을 완료했다. 이걸 트리 구조로 표현해 내면 된다. 트리 구조로 표현 또는 저장 하는 법은 어려운 일이 아니므로 위와 같이 괄호로 묶음을 표현만 하도록 하겠다. 다음부터 설명하는 알고리즘을 이용하면 a가 아니라 d가 먼저 묶이고 a가 맨 나중에 묶이게 된다. 위는 단지 우선순위에 대한 예시이다.

묶음 규칙은 다음과 같다.

1. 맨 앞의 묶음부터 시작한다.

2. 뒤 연산자가 있는지 확인한다.

- 있다면

2. 현재 묶음 앞뒤에 있는 연산자의 우선 순위를 비교한다. ( 앞 연산자가 없는 경우 앞 연산자의 우선 순위는 0이라고 가정한다. )

- 앞 연산자의 우선 순위가 뒷 연산자 보다 낮거나 같다면

3. 뒷 연산자의 다음 부터 묶음을 시작하여 새로운 묶음을 구한다. ( 2번 과정부터 시작하면 된다. )

4. 현재 묶음과 연산자, 새로 구한 묶음을 묶는다.

- 그렇지 않다면

3. 묶음을 멈춘다.

- 없다면

2. 묶음을 멈춘다.

규칙이 이해가 되지 않는다면 일단 다음 예제를 보자. ( 이해가 되었다면 훨씬 좋고! )

예시로 트리 구조를 생성할 표현식을 만들어 보자.

a + b * c - d / e & f.g || false

각 연산자들 밑에 우선순위를 표기하여 보기 쉽게 한다.

이제 맨 앞에서 부터 묶음을 시작해 보자!

맨 앞 묶음은 빨강색으로 표시하겠다.

또한 완료된 묶음은 파랑색으로 표시하겠다.

( a + b * c - d / e & f.g || false

    2   3   2   3   4  5   0      

  ^                               

a 앞에는 연산자가 없으므로 앞 연산자는 우선순위가 0이라고 가정한다.

그리고 a와 같이 연산자를 제외한 모든 요소들은 각각 하나의 완성된 묶음이다. 그러나 파랑색으로 표시하지는 않겠다.

위를 보면 묶음의 앞 연산자의 우선순위가 뒷 연산자인 + 보다 낮으므로 + 다음 묶음 b 부터 묶음을 시작한다.

( a + ( b * c - d / e & f.g || false

    2     3   2   3   4  5   0      

        ^                           

b의 앞 연산자 + 가  * 보다 우선순위가 낮으므로 c 부터 묶음을 시작한다.

( a + ( b * ( c - d / e & f.g || false

    2     3     2   3   4  5   0      

              ^                       

앗! 앞 연산자 * 가 뒷 연산자 - 보다 우선순위가 크다.

c 는 여기서 묶음을 멈추고 b 묶음으로 돌아간다.

( a + ( b * (c) - d / e & f.g || false

    2     3     2   3   4  5   0      

        ^                             

b 는 연산자 뒤의 묶음을 구했으므로 자신과 연산자, 새로 구한 묶음을 묶어 a 묶음으로 돌아간다.

( a + ( b * (c) ) - d / e & f.g || false

    2     3       2   3   4  5   0      

  ^                                     

a 또한 연산자 뒤의 묶음을 구했으므로 자신과 연산자를 묶고 묶음을 멈춘다.

( ( a + ( b * (c) ) ) - d / e & f.g || false

      2     3         2   3   4  5   0      

                    ^                       

맨 앞 묶음부터 다시 시작한다. 알다시피 앞 연산자가 없으므로 앞 연산자의 우선순위는 0 이다. 뒤 연산자 - 보다 우선순위가 낮으므로 d 부터 묶음을 시작한다.

( ( a + ( b * (c) ) ) - ( d / e & f.g || false

      2     3         2     3   4  5   0      

                        ^                   

앞이 뒤보다 우선순위가 낮으므로 e 부터 묶음을 시작한다.

( ( a + ( b * (c) ) ) - ( d / ( e & f.g || false

      2     3         2     3     4  5   0      

                                ^               

앞이 뒤보다 낮으므로 f 부터 묶음을 시작한다.

( ( a + ( b * (c) ) ) - ( d / ( e & ( f.g || false

      2     3         2     3     4    5   0      

                                      ^           

앞이 뒤보다 낮으므로 g 부터 묶음을 시작한다.

( ( a + ( b * (c) ) ) - ( d / ( e & ( f.(g || false

      2     3         2     3     4    5    0      

                                         ^         

드디어 뒤가 앞보다 우선순위가 낮다. 이제 g는 묶음을 멈추고 f 로 돌아간다.

( ( a + ( b * (c) ) ) - ( d / ( e & ( f.(g) || false

      2     3         2     3     4    5     0      

                                      ^             

f 는 연산자 뒤 묶음을 구했으니 묶음을 멈추고 e로 돌아간다.

( ( a + ( b * (c) ) ) - ( d / ( e & ( f.(g) ) || false

      2     3         2     3     4    5       0      

                                ^                     

이제 말 안해도 알거라 믿는다. d로 돌아간다.

( ( a + ( b * (c) ) ) - ( d / ( e & ( f.(g) ) ) || false

      2     3         2     3     4    5         0      

                          ^                             

빨강색 묶음으로 돌아간다.

( ( a + ( b * (c) ) ) - ( d / ( e & ( f.(g) ) ) ) || false

      2     3         2     3     4    5           0      

                    ^                                     

빨강색 묶음은 연산자 뒤 묶음을 구했다. 자신과 연산자, 뒤 묶음을 하나로 묶고 새 묶음을 만든 후 이 묶음부터 다시 묶음을 시작한다.

( ( ( a + ( b * (c) ) ) - ( d / ( e & ( f.(g) ) ) ) ) || false

        2     3         2     3     4    5             0      

                                                    ^         

앞 연산자는 말 안해도 알겠지만 우선순위가 0이다. 다음 연산자 또한 우선 순위가 0이다. 서로 같으므로 false 부터 묶음을 시작한다.

( ( ( a + ( b * (c) ) ) - ( d / ( e & ( f.(g) ) ) ) ) || (false

        2     3         2     3     4    5             0       

                                                            ^  

더이상 묶을 것이 없으므로 묶음을 멈추고 빨강색 묶음으로 돌아온다.

( ( ( a + ( b * (c) ) ) - ( d / ( e & ( f.(g) ) ) ) ) || (false)

        2     3         2     3     4    5             0        

                                                    ^           

빨강색 묶음은 연산자 뒤 묶음을 구했다. 자신과 연산자, 뒤 묶음을 묶고 묶음을 마친다.

( ( ( a + ( b * (c) ) ) - ( d / ( e & ( f.(g) ) ) ) ) || (false) )

        2     3         2     3     4    5             0          

                                                                 ^

빨강색 묶음도 더 이상 묶을것이 없으니 여기서 묶음이 종료된다.

이렇게 묶음을 완료했다. 우선 순위가 높은것이 먼저 묶인다는 기본적인 원리를 그대로 따르는 알고리즘이라고 생각한다.

실제로 코드를 짤때에는 각각의 묶음을 노드라고 생각하고 묶음 안에 있는 연산자와 두개의 묶음을 자식 노드라고 생각한다면 트리구조를 간단히 생성해낼 수 있음을 알 수 있다.

묶음 규칙을 하나의 함수라고 생각하면 재귀적으로 함수가 호출되면서 묶음을 만들어 내게 될 것이다.

그럼 여기서 중위 표기식 트리 구조 생성 알고리즘 포스팅을 완료한다!