생각을 개발하자, 박진형

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

Data structure & Algorithm/data structure_algorithm

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

imjinbro imjinbro 2017.10.17 18:39

[수식트리]

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

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

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

- 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());
}