SWE 1232(사칙연산)

작성일

1232 S/W 문제해결 기본 9일차 - 사칙연산

사칙연산으로 구성되어 있는 식은 이진트리로 표헌할 수 있다. 임의의 정점에 연산자가 있으면 해당 연산자의 왼쪽 서브트리의 결과와 오른쪽 서브트리의 결과를 사용해서 해당 연산자를 적용한다. 사칙연산 “+,-,*,/”와 양의 정수로만 임의의 이진트리가 주어질 때, 이를 계산한 결과를 출력하는 프로그램을 작성하라 단, 중간 과정 에서의 연산은 실수 연산으로 하되, 최종 결과값이 정수로 떨어지지 않으면 정수부만 출력한다.

해설

이전에 풀었던 문제와 상당히 동일하다.

사칙연산 이진 트리의 조건을 다시 언급 하자면, 다음과 같다

  • 연산자 노드가 가지는 서브 트리는 두 개의 서브트리가 존재해야 한다.
  • 숫자 노드가 가지는 서브 트리는 두 개의 서브 트리가 존재해야 한다.

이전의 문제는 중위 순회로 접근했다

이 문제는 왼쪽 서브 트리와 오른쪽 서브 트리를 방문한 다음, 자신의 노드는 연산자가 되므로 이 때 계산을 해야 한다. 자신의 노드 left,right 값을 접근할 수 있기 때문에 후위 순회를 하면 된다.

생각하기

이 문제는, 이전에 풀었던 배열로 접근할 수가 없다. 왜냐하면 완전 이진트리가 아니기 때문이다. 따라서 트리를 구성해야 한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Node{
	String item;
	int left;
	int right;
	
	public Node (String item, int left, int right) {
		this.item = item;
		this.left = left;
		this.right = right;
	}
}


public class Solution {
	
	static Node[] tree;
	
	static int T = 1;
	static int N;
	
	public static void main(String args[]) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int var1, var2, no;
		int t = 1;
		String item;
		
		while(T-- > 0) {
			N = Integer.parseInt(br.readLine()); // 정점의 총 수 저장
			
			tree = new Node[N + 1];
			
			for(int i = 0 ; i < N ; i ++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				
				no = Integer.parseInt(st.nextToken());
				item = st.nextToken();
				
				if(st.hasMoreTokens()) {
					tree[no] = new Node(item, Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
				}
				else {
					tree[no] = new Node(item, 0, 0);
				}
			}
			
			for(int i = N; i >= 1; i--) {
				
				if(tree[i].left != 0) {
					
					var1 = Integer.parseInt(tree[tree[i].left].item);
					var2 = Integer.parseInt(tree[tree[i].right].item);
					
					switch(tree[i].item) {
					
					case "+":
						tree[i].item = String.valueOf((var1+var2));
						break;
					
					case "-":
	
						tree[i].item = String.valueOf((var1 - var2));
						break;
	
					case "*":
	
						tree[i].item = String.valueOf((var1 * var2));
						break;
	
					case "/":
	
						tree[i].item = String.valueOf((var1 / var2));
						break;
					}
				}
			}
			
			
			System.out.println("#" + (t++) + " " + tree[1].item);
		}
		br.close();
	};
	
	
}

참고자료

SWE selfStudyBook(3)

https://github.com/Karmantez/SWExpertAcademy/blob/master/1232%EC%82%AC%EC%B9%99%EC%97%B0%EC%82%B0/src/Solution.java

0%