[자료구조] 수식 트리 계산 프로그램

이진 트리는 수식 트리(expression tree)를 처리하는데 사용될 수 있다.
수식 트리는 기본적으로 연산자(+, -, *, / 등)와 피연산자(정수, 실수 등)으로 만들어진다.
피연산자들은 단말노드가 되며 연산자는 비단말 노드가 된다.

스택을 이용한 후위 표기 수식을 떠올려보자.
피연산자이면 스택에 삽입하고, 연산자이면 스택에서 필요한 수만큼의 피연산자를 꺼내 연산을 실행하고,
그 연산 결과를 다시 스택에 넣는 방법이었다.


이번에는 후위 표기 수식이 아닌, '수식 트리'의 구조로 수식이 표현된다.
수식 트리의 루트 노드는 연산자이고, 연산자의 피연산자인 자식 노드들을 계산하여 전체 수식을 계산해보자.
루트 노드보다 자식 노드들을 먼저 방문하는 후위 순회 방법을 사용하여 계산을 진행해보자.

/* * 수식 트리 계산 프로그램 */ #include <stdio.h> #include <stdlib.h> // 이진 트리 노드 구조체 typedef struct TreeNode { int data; struct TreeNode* left, * right; }TreeNode; // + // * + // 1 4 16 25 // // (1*4) + (16+25) TreeNode n1 = { 1, NULL, NULL }; TreeNode n2 = { 4, NULL, NULL }; TreeNode n3 = { '*', &n1, &n2 }; TreeNode n4 = { 16, NULL, NULL }; TreeNode n5 = { 25, NULL, NULL}; TreeNode n6 = { '+', &n4, &n5 }; TreeNode n7 = { '+', &n3, &n6 }; TreeNode* exp = &n7; // 수식 계산 함수 int evaluate(TreeNode* root) { int op1, op2; if (root == NULL) return 0; if (root->left == NULL && root->right == NULL) return root->data; else { op1 = evaluate(root->left); op2 = evaluate(root->right); printf("%d %c %d 을 계산합니다. \n", op1, root->data, op2); switch (root->data) { case '+': return op1 + op2; case '-': return op1 - op2; case '*': return op1 * op2; case '/': return op1 / op2; } } return 0; } int main() { printf("수식의 값은 %d입니다. \n", evaluate(exp)); }

// + // * + // 1 4 / 25 // 6 3 // (1*4) + (6 / 3) + 25 = 4 + 2 + 25 = 31 TreeNode n1 = { 1, NULL, NULL }; TreeNode n2 = { 4, NULL, NULL }; TreeNode n3 = { '*', &n1, &n2 }; TreeNode n4 = { 6, NULL, NULL }; TreeNode n5 = { 3, NULL, NULL}; TreeNode n6 = { '/', &n4, &n5 }; TreeNode n7 = { 25, NULL, NULL }; TreeNode n8 = { '+', &n6, &n7 }; TreeNode n9 = { '+', &n3, &n8 }; TreeNode* exp = &n9;