이진 트리를 이용해서 수식을 표현해 놓은 것을 가리켜 ‘수식 트리’라 한다. 즉 수식 트리는 이진 트리와 구분이 되는 별개의 것이 아니다.
7 + 4 * 2 - 1
컴파일러는 이런 수식을 어떻게 처리 할까?
“루트 노드의 저장된 연산자의 연산을 하되, 두 개의 자식 노드에 저장된 두 피연산자를 대상으로 연산을 한다.” - abstract syntax tree, ast
수식 트리의 구성을 위해서는 후위 표기법의 다음 두 가지 특징을 인지하고 있어야 한다.
그런데 수식 트리에서는 트리의 아래쪽에 위치한 연산자들의 연산이 먼저 진행된다. 때문에 후위 표기법의 수식에서 먼저 등장하는 피연산자와 연산자를 이용해서 트리의 하단을 만들고, 이를 바탕으로 점진적으로 트리의 윗부분을 구성해 나가야 한다.
스택을 사용하여 연산자가 올 시 2개의 피연산자를 뺴내서 하나의 트리를 만들어 주면 된다. 이 과정에서 만들어진 트리는 다시 스택에 넣어야하는데 서브트리의 연산자만 넣으면 자식노드 들은 연결이 되어 있으니 연산자의 주소만 스택으로 옮기면 된다.
위를 정리하면 다음과 같다.
두개의 피연산자는 노드가 될수도 있고 트리가 될수도 있다.
