수식 트리(Expression Tree)의 구현

수식 트리

수식 트리의 이해

수식 트리는 이진 트리를 이용해서 수식을 표현해 놓은 것을 말한다. 따라서 수식 트리와 이진 트리는 구분이 되는 별개의 것이 아니다. 

일반적으로 7 + 4 * 2 - 1과 같은 인간이 보기 좋은 수식(중위 표기법)은 컴퓨터가 이해하기 어렵다. 따라서 컴파일러는 이와 같은 수식을 수식 트리로 재 표현한 다음에 계산한다. 왜냐하면 수식 트리는 연산 과정에서 우선순위를 고려하지 않기 때문에 해석이 쉽기 때문이다. 아래는 중위 표기법을 수식 트리로 재 표현한 모습이다.

수식 트리의 계산 순서는 다음과 같다.

이렇듯 수식 트리는 연산의 순서가 명확하고, 연산의 과정을 쉽게 파악할 수 있는 이진 트리의 일종이다. 

중위 표기법을 수식트리까지 옮기는 과정은 아래와 같다.

중위 표기법 -> 후위 표기법 -> 스택 -> 수식 트리

여기서 후위 표기법을 수식 트리로 옮기는 방법은 아래를 봐 보자.

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

이 글은 열혈 자료구조를 읽고 정리한 글입니다.