조건
1. 트리를 이용해서 구현한다.
2. 트리에 저장될 노드 데이터는 임의로 완전이진 트리 형태를 갖추도록 데이터를 넣는다.
3. 트리의 연산은 후위순회를 통하여 후위표기법과 동일한 알고리즘을 탈수 있게 한다.
구현상 어려웠던점
이 역시 괄호를 이용한 연산자 우선순위를 처리 하는 부분과 그리고 무엇보다 트리형태로 데이터를 배치(정렬)하게 하는게 쉽지 않다.
현 예제는 강제로 완전이진트리를 갖추게 데이터를 배치 하였지만 임의의 데이터(일련의 표현식들)가 들어왔을때 이를 과연 쉽게
이진 트리 형태로 정렬해주고 이를 통해 결과를 얻어 내려면 상당한 알고리즘 능력이 요구될거로 보인다.(난 못했다 )
조심스런 결론을 내어보자면 예제이기 때문에 만들기는 했지만 일련의 표현식을 통한 계산을 처리하는 알고리즘에
트리의 사용은 그다지 효율적으로 보이지 않는다. 차라리 스택이 빠르고 편하며 직관적이다.
h3.중위 표기법 과 후위 표기법
중위 표기법
후위 표기법
설명
중위 표기법을 후위 표기법으로 바꾸는 과정
A*B-C/D
1단계 : ((A*B)-(C/D))
2단계 : (AB)*-(CD)/)-
3단계 : AB*CD/-
컴퓨터 내부에서 수식을 처리하기에 가장 효율적인 코드는 후위 표기식이다.
후위 표기식은 괄호나 연산자 우선순위를 따로 처리 하지 않고 왼쪽에서 오른쪽으로 표기된 순서대로 처리 할수 있다.
public class LinkedTree {
private StringBuffer preOrderStrBuf;
private StringBuffer inOrderStrBuf;
private StringBuffer postOrderStrBuf;
public LinkedTree() {
this.preOrderStrBuf = new StringBuffer();
this.inOrderStrBuf = new StringBuffer();
this.postOrderStrBuf = new StringBuffer();
}
public TreeNode makeTree(TreeNode leftNode, Object data, TreeNode rightNode) {
TreeNode nRoot = new TreeNode();
nRoot.data = data;
nRoot.left = leftNode;
nRoot.right= rightNode;
return nRoot;
}
public void preOrder(TreeNode root) {
if (root != null) {
preOrderStrBuf.append((String)root.data);
preOrder(root.left);
preOrder(root.right);
}
}
public void inOrder(TreeNode root) {
if(root != null){
inOrder(root.left);
inOrderStrBuf.append((String)root.data);
inOrder(root.right);
}
}
public void postOrder(TreeNode root) {
if (root != null) {
postOrder(root.left);
postOrder(root.right);
postOrderStrBuf.append((String)root.data);
}
}
public String getPreOrderStrBuf() {
String rtnVale = preOrderStrBuf.toString();
this.preOrderStrBuf.setLength(0);
return rtnVale;
}
public String getInOrderStrBuf() {
String rtnVale = inOrderStrBuf.toString();
this.inOrderStrBuf.setLength(0);
return rtnVale;
}
public String getPostOrderStrBuf() {
String rtnVale = postOrderStrBuf.toString();
this.postOrderStrBuf.setLength(0);
return rtnVale;
}
}
public class LinkedTreeMain {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
LinkedTree lt = new LinkedTree();
LinkedListStackCalc llsc = new LinkedListStackCalc();
//(6*9)-(9/3)
TreeNode operation7 = lt.makeTree(null, "3", null);
TreeNode operation6 = lt.makeTree(null, "9", null);
TreeNode operation5 = lt.makeTree(null, "9", null);
TreeNode operation4 = lt.makeTree(null, "6", null);
TreeNode operation3 = lt.makeTree(operation6, "/", operation7);
TreeNode operation2 = lt.makeTree(operation4, "*", operation5);
TreeNode operation1 = lt.makeTree(operation2, "-", operation3);
System.out.println("preOrder : ");
lt.preOrder(operation1);
System.out.println(lt.getPreOrderStrBuf());
System.out.println("lt.inOrder : ");
lt.inOrder(operation1);
System.out.println(lt.getInOrderStrBuf());
System.out.println("lt.postOrder : ");
lt.postOrder(operation1);
String tmp = lt.getPostOrderStrBuf();
System.out.println("표현식 : " +tmp);
System.out.println("결과 : " + llsc.evalPostPix(tmp));
}
}
이외의 또다른 TREE 예제를 살펴 보자면
선웅형이 예전에 패턴스터디 할때 만들어 두었던 XMLTREE 예제 를 살펴보면 많은 도움이 될듯하다.