[SWEA] 1232. 사칙연산 - 트리(java)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV141J8KAIcCFAYD 

SW Expert Academy

 

 

 

위 트리는 식 (9/(6-4))*3을 이진트리로 표현한 것이고 이를 계산한 값을 출력하면 된다.

사람들은 사칙 연산을 할 때(9/(6-4))*3식과 같은 중위 표기식으로 계산을 한다. 하지만 컴퓨터를 통해 각 연산자의 우선순위대로 계산을 하려면 후위 표기식으로 변환해 계산해야 한다.

즉 (9/(64))*3 → 964-/3*으로 변환되고 이를 계산한다.

따라서 해당 문제에서는 트리를 입력받고 후위 순회하며 각 단계에서 계산을 해주면 된다.

 

 

매우 중요한 트리의 순회 동작 순서

위와 같은 트리가 있다고 한다면 각각 순회방법은 다음과 같다.

• 전위 순회 : 0->1->3->7->8->4->9->10->2->5->11->6
• 중위 순회 : 7->3->8->1->9->4->10->0->11->5->2->6
• 후위 순회 : 7->8->3->9->10->4->1->11->5->6->2->0
• 층별 순회 : 0->1->2->3->4->5->6->7->8->9->10->11

★전위 순회는 뿌리->왼쪽 자식->오른쪽 자식 순

 

★중위 순회는 왼쪽자식-> 뿌리-> 오른쪽 자식

 

★후위 순회는 왼쪽자식->오른쪽 자식-> 뿌리

 

★층별 순회는 그냥 노드의 순서대로

 

핵심

트리에서 후위 표기식 계산 방법

스택을 이용해 계산하면 된다.

1. 숫자일 경우 바로 스택에 넣는다.
2. 연산자일 경우 스택에 담긴 두 개의 피연산자를 꺼내 연산 후 다시 스택에 넣는다.
3. 탐색이 종료되면 스택에 남은 최종 값이 연산의 결괏값이 된다.

이를 활용해 풀어보자.

 

 

정답 코드

class Solution {
    static int N;
    static StringBuilder sb;
    static List<Node> nodes = new ArrayList<>();
    static Stack<Double> stack;

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

        int T = 1;

        for(int test_case = 1; test_case <= T; test_case++) {
            N = Integer.parseInt(br.readLine());
            nodes = new ArrayList<>();
            stack = new Stack<>();

            for (int i = 0; i <=N; i++) {
                Node n = new Node();
                nodes.add(n);
            }

            for (int i = 1; i <=N; i++){
                String[] str = br.readLine().split(" ");
                Node node = nodes.get(Integer.parseInt(str[0]));
                if (str.length==4){
                    node.value = str[1];
                    node.left = nodes.get(Integer.parseInt(str[2]));
                    node.right = nodes.get(Integer.parseInt(str[3]));
                }else {
                    node.value = str[1];
                }
            }
            postOrder(nodes.get(1));
            int result = stack.pop().intValue();
            sb.append("#").append(test_case).append(" ").append(result).append("\n");
        }
        System.out.println(sb.toString());

    }

    public static void postOrder(Node node){
        if (node.left==null||node.right==null){
            getResult(node.value);
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        getResult(node.value);
    }

    public static void getResult(String v){
        if (!(v.equals("+")||v.equals("-")||v.equals("*") ||v.equals("/"))){
            stack.push(Double.parseDouble(v));
            return;
        }
        Double b = stack.pop();
        Double a = stack.pop();
        if (v.equals("+")) stack.push(a + b);
        else if (v.equals("-")) stack.push(a - b);
        else if (v.equals("/")) stack.push(a / b);
        else stack.push(a * b);

    }

    static class Node{
        private String value;
        private Node left;
        private Node right;
    }
}

해설

Node라는 클래스를 만들어서 각각의 노드의 값과 왼쪽 자식, 오른쪽 자식을 넣어주었다.

후위순회를 돌리며, value값을 getResult에 넣어주었다.

후위순회이므로 숫자가 2번 들어오고, 연산식이 들어오는 방식이다.

Stack을 사용하여 숫자들을 집어넣고, 연산식이 오면 숫자 2개를 빼서 계산한 뒤 다시 넣어준다.

 

 

배운 점

트리의 순회에 따라 풀이가 달라질 수 있다는 것을 알았다.

기존에는 중위순회만 익히고 다른 순회에 대해 부족했다.

따라서 이 문제를 풀 때 처음에 고민을 많이 하였다.

트리의 여러 가지  순회를 익히면, 여러 문제를 풀 때 사용할 수 있을 것 같다.