[자료구조 알고리즘] 이진트리 - 수식트리 만들기

[수식트리]

- 수식을 여러가지로 표현하기위해서 구성해놓는 트리 : 이진트리(연산자 < 피연산자, 피연산자)

- 전위, 중위, 후위표기법을 나타낼 수 있음 : 이진트리 순회 방법에 따라

- 후위표기법을 트리로 변환, 중위표기법을 경우 후위표기법으로 변환한 후 트리로 변환

- BTreeNode : 이진트리 만드는 도구이자 이진트리의 루트노드(서브까지)로 만듬

import java.util.Stack;

public class ExpressionTree {

    private BTreeNode root;

    public BTreeNode getExpressionTree(String exp) {
        /* 후위표기법 -> 수식 트리로 변경 : 수식트리의 루트노드만 리턴받으면 됨 */
        char[] data = exp.toCharArray();
        int length = data.length;

        Stack temp = new Stack();
        for (int i = 0; i < length; i++) {
            char target = data[i];

            if(target >= '0' && target <= '9'){
                temp.push(target);
            } else {
                BTreeNode newNode = new BTreeNode(target);

                Object sub = temp.pop();
                newNode.setRightSubTree(sub instanceof BTreeNode ? (BTreeNode)sub : new BTreeNode(sub));
                sub = temp.pop();
                newNode.setLeftSubTree(sub instanceof BTreeNode ? (BTreeNode)sub : new BTreeNode(sub));
                temp.push(newNode);
            }
        }

        root = (BTreeNode)temp.pop();
        return root;
    }


    public int getResult(BTreeNode root){
        if(root.getLeftSubTree() == null && root.getRightSubTree() == null){
            return Integer.parseInt(root.getData().toString());
        }

        int left = getResult(root.getLeftSubTree());
        int right = getResult(root.getRightSubTree());

        switch((char)root.getData()){
            case '+':
                return left+right;

            case '-':
                return left-right;

            case '*':
                return left*right;

            case '/':
                return left/right;
        }

        return 0;
    }


    public void getPrefix(BTreeNode root){
        BTreeNode.preorderTreverse(root);
    }

    public void getInfix(BTreeNode root){
        BTreeNode.inorderTraverse(root);
    }

    public void getPostfix(BTreeNode root){
        BTreeNode.postorderTreverse(root);
    }

}



/* BTreeNode 표기법 관련 코드 : 순회 순서만 변경해주면 됨 */
public static void preorderTreverse(BTreeNode root){
    if(root == null){
        return;
    }

    System.out.print(root.getData());
    preorderTreverse(root.getLeftSubTree());
    preorderTreverse(root.getRightSubTree());
}

public static void inorderTraverse(BTreeNode root){
    /* [이진트리 관점] */
    if(root == null){
        return;
    }

    inorderTraverse(root.getLeftSubTree());
    System.out.print(root.getData());
    inorderTraverse(root.getRightSubTree());

    /*
    [단순 노드 관점]
    if(root.leftSubTree != null){
        Traverse(root.leftSubTree);
    }
    System.out.println(root.getData());
    if(root.rightSubTree != null){
        Traverse(root.rightSubTree);
     }
     */
}

public static void postorderTreverse(BTreeNode root){
    if(root == null){
        return;
    }

    postorderTreverse(root.getLeftSubTree());
    postorderTreverse(root.getRightSubTree());
    System.out.print(root.getData());
}