수식 트리 (Expression Tree)
글 작성자: NoHack
728x90
Expression Tree 🙂
수식 트리(Expression Tree)는 이진 트리를 활용한 대표적인 케이스입니다. 수식 트리를 만들기 위해서는 몇 가지 조건을 충족해야 합니다. 하나의 연산자가 두 개의 피연산자를 취한다는 가정 하에 피연산자는 무조건 잎 노드여야 하며, 연산자는 가지 또는 루트 노드여야 합니다. 수식 트리는 후위 표현식을 사용하면 쉽게 만들 수 있는데, 후위 표현식을 뒤에서부터 분해하여 하나씩 노드로 만들어 연결하면 됩니다.
본문의 수식 트리는 하나의 연산자가 무조건 두 개의 피연산자를 취한다는 가정을 하고 구현했습니다.
노드 생성
function Node(data) {
this.data = data;
this.left = null;
this.right = null;
}
수식 트리는 이진 트리에 기반하므로, Node는 동일한 멤버 변수를 갖습니다.
수식 트리 생성
const build = (stack, node) => {
const token = stack.pop();
switch (token) {
case '+':
case '-':
case '*':
case '/':
node.data = token;
node.left = new Node();
node.right = new Node();
// 오른쪽부터 트리 구성
build(stack, node.right);
build(stack, node.left);
default:
node.data = token;
}
};
저는 후위 표현식을 수식 트리로 만들기 위해 스택 구조를 이용했습니다. 맨 뒤의 문자를 스택에서 뺀 다음, 토큰이라는 변수에 저장하여 switch로 연산자인지, 피연산자인지 체크했습니다. 연산자라면 노드의 데이터를 토큰으로 할당해 주고, 두 개의 빈 자식 노드를 생성하여 다시금 재귀 호출했습니다. 그리고 피연산자의 경우에는 그냥 노드의 데이터만 토큰으로 할당한 다음 종료했습니다.
수식 트리 계산
const calculate = (node) => {
if (node === null) return;
let result;
switch (node.data) {
case '+':
case '-':
case '*':
case '/':
let left = calculate(node.left);
let right = calculate(node.right);
if (node.data === '+') result = left + right;
else if (node.data === '-') result = left - right;
else if (node.data === '*') result = left * right;
else if (node.data === '/') result = left / right;
break;
default:
return node.data;
}
return result;
};
수식 트리를 계산하는 것도 동일하게 switch와 재귀 함수를 이용해 구현했습니다. 크게 어려운 부분은 없습니다.
References 📝
본문의 내용은 GeeksforGeeks의 Expression Tree 자료를 참고해 작성했습니다 ❤️
'💻 컴퓨터공학 > 자료구조' 카테고리의 다른 글
힙 (Heap) (0) | 2021.10.29 |
---|---|
분리 집합 (Disjoint Set) (0) | 2021.10.26 |
이진 트리 (Binary Tree) (0) | 2021.10.26 |
LCRS 트리 (LCRS Tree) (0) | 2021.10.25 |
큐 (Queue) (0) | 2021.10.14 |
댓글
이 글 공유하기
다른 글
-
힙 (Heap)
힙 (Heap)
2021.10.29 -
분리 집합 (Disjoint Set)
분리 집합 (Disjoint Set)
2021.10.26 -
이진 트리 (Binary Tree)
이진 트리 (Binary Tree)
2021.10.26 -
LCRS 트리 (LCRS Tree)
LCRS 트리 (LCRS Tree)
2021.10.25