수식 트리, expression tree

package data_structure.tree;

import java.util.Stack;

/*
 * 수식 트리 구축, 계산, 출력 구현
 *	- 수식은 후위표기식으로 입력되며 연산자와 피연산자들은 공백 하나로 구분된다고 가정.
 */

public class ExpressionTree {

	public static class Node<E>{
		E data;
		Node<E> left;
		Node<E> right;
		public Node(E data) {
			this.data = data;
			left = null;
			right = null;
		}
	}

	/*
	 * <수식트리 구축>
	 *
	 * 후위 표기식을 앞에서부터 읽어가면서,
	 * 1. 토큰이 연산자인 경우 스택의 최상위 노드 두개를 꺼내 순서대로 연산자 노드의 오른쪽, 왼쪽 자식으로 만든다.
	 * 2. 토큰이 피연산자(숫자)인 경우 노드를 만들어 스택에 담는다.
	 *
	 * 위 과정을 수식을 다 읽을 때 까지 반복한다.
	 *
	 * "모든 과정 완료 후에 스택에는 루트노드에 대한 정보만 남아 있게 된다."
	 */
	public Node<String>  build(String expression) {

		String[] postfix = expression.split(" ");
		Stack<Node<String>> treeStack = new Stack<>();

		for (int i = 0; i < postfix.length; i++) {

			String token = postfix[i];

			switch (token) {
			case "+": case "-": case "*":case "/":

				Node<String> newnode = new Node<String>(token);

				newnode.right = treeStack.pop();
				newnode.left = treeStack.pop();

				treeStack.push(newnode);

				break;

			default:
				//피연산자인 경우
				treeStack.push(new Node<String>(token));

				break;
			}

		}

		return treeStack.peek();

	}


	//트리 출력 (후위순회)
	public void postorder(Node<String> node) {
		if(node == null)
			return;

		postorder(node.left);
		postorder(node.right);
		System.out.println(node.data);
	}

	/*
	 * <수식 트리 계산>
	 * 노드의 데이터가 연산자인 경우, 재귀호출을 통해서 해당 연산자 결과 값을 얻는다.
	 * 따라서, 피연산자인 Leaf노드에 도달할 때 까지 재귀호출이 반복된다.
	 */
	public double evaluate(Node<String> node) {

		double left = 0;
		double right = 0;

		if(node == null)
			return 0;

		switch (node.data) {
		case "+": case "-": case "*": case "/":

			left = evaluate(node.left);
			right = evaluate(node.right);

			if(node.data.equals("+")) {
				return left + right;
			} else if(node.data.equals("-")) {
				return left - right;
			} else if(node.data.equals("*")) {
				return left * right;
			} else if(node.data.equals("/")) {
				return left / right;
			}

		default:

			return Double.parseDouble(node.data);
		}

	}