【Java】 자바로 이진트리와 수식 계산

자바로 이진트리와 수식 계산

 

추천글 : 【Java】 Java 목차

---

 

 

Q. 수식이 입력되면 수식의 결과를 출력하는 계산기를 만들자.

 

Ex. 입력: 24+4*(5-3), 출력: 32

 

Step1. 수식계산 알고리즘을 이진트리로 접근해 보자. 1)에서 8) 순으로 조건문을 적용한다.

1) 각 연산자의 서열은 다음과 같다;    + > - > * > / > (, ) > 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

2) 어떤 노드에 특정 연산자를 추가할 때 그 노드가 null이면 그 노드는 그 연산자를 저장하는 새로운 노드가 된다.

3) '('를 저장하는 노드에 ')' 이외의 연산자를 추가할 때 왼쪽 자식노드에 그 연산자를 추가한다.

4) '('를 저장하는 노드에 연산자 ')'를 추가할 때 두 괄호 사이의 부분을 미리 계산한다.

5) 어떤 노드에 특정 연산자를 추가할 때 그 노드가 루트인 트리가 '('를 포함하면 오른쪽 자식노드에 연산자를 추가한다.

cf. 괄호는 사칙연산자보다 서열이 낮으므로 왼쪽에 있지 않다.

6) 어떤 노드에 특정 연산자를 추가할 때 그 연산자가 그 노드의 연산자보다 더 서열이 높으면 그 노드로의 포인터는 그 연산자를 저장하는 새로운 노드가 되고, 기존 노드는 새로운 노드의 왼쪽 자식노드(left children node)가 된다.

7) '('를 저장하지 않는 어떤 노드에 특정 연산자를 추가할 때 그 연산자가 그 노드의 연산자보다 서열이 크지 않고, 그 노드의 왼쪽 자식노드가 없을 때 그 노드의 왼쪽 자식노드에 그 연산자를 추가한다.

8) '('를 저장하지 않는 어떤 노드에 특정 연산자를 추가할 때 그 연산자가 그 노드의 연산자보다 서열이 크지 않고, 그 노드의 왼쪽 자식노드가 존재할 때 그 노드의 오른쪽 자식노드에 그 연산자를 추가한다. 

 

Step 2. 위 재귀조건을 그대로 코딩 재귀적으로 계산 알고리즘 규칙

 

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        String str = scan.nextLine();
        String str2 = "";
        int i = 0;  IntTreeNode root;   IntTree tree;
        
        // str starts with '-'
        if(str.charAt(0) == '-'){
            root = new IntTreeNode("0");
            tree = new IntTree(root);
            i = 1;
            tree.add("-");
        }       
        // str starts with number
        else{
            for(; i < str.length(); i ++){
                if(str.charAt(i) >= '0' && str.charAt(i) <= '9')
                    str2 += str.charAt(i) - '0';
                else    break;
            }           
            root = new IntTreeNode(str2);
            tree = new IntTree(root);
        }

        for(; i < str.length(); i ++){
            if(str.charAt(i) >= '0' && str.charAt(i) <= '9'){
                str2 = "";
                for(; i < str.length(); i ++){
                    if(str.charAt(i) >= '0' && str.charAt(i) <= '9')
                        str2 += str.charAt(i) - '0';
                    else    {
                        i --;
                        break;  
                    }
                }
                tree.add(str2);
            }
            else if(str.charAt(i) == '(')   tree.add("(");
            else if(str.charAt(i) == ')')   tree.add(")");
            else if(str.charAt(i) == '+')   tree.add("+");
            else if(str.charAt(i) == '-')   tree.add("-");
            else if(str.charAt(i) == '*')   tree.add("*");
            else if(str.charAt(i) == '/')   tree.add("/");
        }
        System.out.println(tree.print());
    }
}

class IntTreeNode {
    public String data;
    public IntTreeNode left;
    public IntTreeNode right;
    
    public IntTreeNode(String data){
        this(data, null, null);
    }
    public IntTreeNode(String data, IntTreeNode left, IntTreeNode right){
        this.data = data;
        this.left = left;
        this.right = right;
    }
}

class IntTree{
    private IntTreeNode overallRoot;
    
    public IntTree(IntTreeNode root){
        overallRoot = root;
    }
        
    public boolean hasBracket(){
        return hasBracket(overallRoot);
    }
    
    private boolean hasBracket(IntTreeNode root){
        if(root == null || root.data.length() == 0) return false;
        if(root.data.charAt(0) == '(')  return true;
        return hasBracket(root.left) | hasBracket(root.right);
    }

    public int print(){
        return print(overallRoot);
    }
    
    private int print(IntTreeNode root){
        if(root == null)    return 0;
        if(root.data.charAt(0) >= '0' && root.data.charAt(0) <= '9'){
            Scanner scan = new Scanner(root.data);
            return scan.nextInt();          
        }
        if(root.data.charAt(0) == '+'){
            return print(root.left) + print(root.right);
        }
        if(root.data.charAt(0) == '-')
            return print(root.left) - print(root.right);
        if(root.data.charAt(0) == '*')
            return print(root.left) * print(root.right);
        if(root.data.charAt(0) == '/')
            return print(root.left) / print(root.right);
        return 0;
    }
    
    
    public void add(String value){
        overallRoot = add(overallRoot, value);
    }
    
    private IntTreeNode add(IntTreeNode root, String value){
        if(root == null || root.data.length() == 0){
            root = new IntTreeNode(value);
        }   else if(root.data.charAt(0) == '('  && value.charAt(0) != ')'){
            root.left = add(root.left, value);
        }   else if(root.data.charAt(0) == '(' && value.charAt(0) == ')'){
            if(!hasBracket(root.left)){
                int data = print(root.left);
                if(data < 0){
                    data *= -1;
                    root.right = new IntTreeNode(intToString(data));
                    root.data = "-";
                    root.left = null;
                }
                else{
                    root.data = intToString(data);
                    root.left = null;                                   
                }
            }
            else{
                root.left = add(root.left, value);              
            }
        }   else if(hasBracket(root)){
            root.right = add(root.right, value);
        }   else if(category(root.data.charAt(0)) < category(value.charAt(0))){
            IntTreeNode node = new IntTreeNode(value);
            node.left = root;
            return node;
        }   else if(root.data.charAt(0) != '(' 
                    && category(root.data.charAt(0)) >= category(value.charAt(0)) 
                    && root.left == null){
            root.left = add(root.left, value);
        }   else if(root.data.charAt(0) != '(' 
                    && category(root.data.charAt(0)) >= category(value.charAt(0)) 
                    && root.left != null){
            root.right = add(root.right, value);
        }
        return root;
    }   

    public int category(char c){
        if(c == '+')    return 6;
        if(c == '-')    return 5;
        if(c == '*')    return 4;
        if(c == '/')    return 3;
        if(c == '(' || c == ')')
            return 2;
        if(c >= '0' && c <= '9')
            return 1;
        return 0;
    }
    public String intToString(int n){
        String str = "";
        while(n > 0){
            str = (n % 10) + str;
            n /= 10;
        }
        return str;
    }
}

 

입력 : 2016.12.11 01:54