[자료구조] Tree(트리) - 수식 트리

2 + 1 * 3 을 트리로 계산하고자 한다.

 

먼저, 수식을 트리로 표현하면 다음과 같다. 

트리를 중위 순회한 결과가 2 + 1 * 3이다.

이 수식을 계산하기 위해서는 중위 순회로 표현된 것을 후위 순회로 바꾸어 주어야 한다.

 

1. 중위 수식에서 후위 수식으로

 

먼저, 중위 수식에서 후위 수식으로 바꾸기 위해서 스택을 사용할 것이다.

규칙은 다음과 같다.

• 피연산자라면 배열에 저장한다.
• 연산자라면 우선순위를 비교해 스택에 넣는다.
  • 스택에 있는 연산자의 우선순위가 높은 경우 : 우선순위가 높은 연산자를 꺼내어 배열에 저장하고 우선순위가 낮은 연산자를 스택에 넣는다.
  • 스택에 있는 연산자의 우선순위가 낮은 경우 : 스택에 넣는다.

 

예시는 다음과 같다.

 

1) 초기 상태의 모습이다. 

2) 2는 피연산자이므로 배열에 저장한다.

3) +는 연산자이므로 스택에 넣는다. (스택에 비어있으므로 우선순위를 비교할 연산자가 없음)

4) 1은 피연산자이므로 배열에 저장한다.

5) *은 연산자이므로 스택에 넣는다. 스택에 + 연산자가 있으므로 우선순위를 비교한다.

    * 연산자의 우선순위가 더 높으므로 그대로 스택에 저장한다.

 

6) 3은 피연산자이므로 배열에 저장한다.

 

7) 더 이상 없으므로 스택에 있는 연산자를 모두 꺼낸다.

따라서, 2 + 1 * 3을 후위 순회로 바꾸면 2 1 3 * + 임을 알 수 있다.

 

 

2. 후위 수식 계산

 

중위 순회에서 후위 순회로 바꾸었으니 이제 계산만 하면 된다.

 

계산하는 방법은 다음과 같다.

• 피연산자라면 스택에 저장한다,
• 연산자라면 스택에서 2개의 피연산자를 꺼내어 계산한다.
• 계산한 값을 다시 스택에 넣는다.

 

 

예시를 살펴보자.

 

 

1) 2는 피연산자이므로 스택에 넣는다.

 

2) 1은 피연산자이므로 스택에 넣는다.

3) 3은 피연산자이므로 스택에 넣는다.

4) *은 연산자이므로 스택에서 피연산자 2개를 꺼내어 계산한다.

 

5) 계산한 결과를 스택에 다시 넣는다.

 

6) +는 연산자이므로 스택에서 2개의 피연산자를 꺼내어 계산한다.

 

7) 계산한 값을 스택에 다시 넣는다. 

 

따라서 2 1 3 * +를 계산한 결과는 5이다.

 

다시 보면, 2 1 3 * + 에서 연산자 전의 2개의 피연산자를 계산하면 된다.

같은 예로 2 1 3 * +는1 3 *를 계산해 2 3 +가 된다. 다시 연산자 전의 2개의 피연산자를 계산하면 5이다.