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

사칙연산

사칙연산으로 구성되어 있는 식을 이진트리로 표현한다.

임의의 정점에 연산자가 있으면 해당 연산자의 왼쪽, 오른쪽 서브트리의 결과를 사용해서 연산자를 적용한다.

사칙연산 “+, -, *, /”와 양의 정수로만 구성된 임의의 이진트리가 주어질 때, 이를 계산한 결과를 출력하는 프로그램을 작성하라.

---

풀이

재귀를 이용해서 서브트리의 값을 구해서 최종 결과를 구해야 한다.

각 노드의 정보를 저장하기 위해서 Node객체를 생성한다.

Node객체에는 노드번호, 노드의 값, 왼쪽자식의 번호, 오른쪽자식의 번호를 저장한다.

leaf노드일 경우에는 자식의 번호를 0으로 설정해 주었다.

입력을 받을 때 stringtokenizer의 토큰 개수를 기준으로 leaf노드와 연산자노드를 구별했다.

노드 배열을 1부터 시작하여 검색이 쉽도록 구현했다.

계산 메소드는 노드를 파라미터로 받고 자식노드의 주소가 0이 아니면 연산자 노드로 판별한다.

여기서 연산자마다 왼쪽,오른쪽 노드의 결과를 재귀로 호출한다.

만약 leaf노드라면 노드의 값을 리턴한다.

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

public class Solution {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
		for(int tc = 1; tc <= 10; tc++ ) {
			int N = Integer.parseInt(br.readLine());
			
			nodes = new Node[N+1];
			
			for(int i = 1; i <= N; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine(), " ");
				int check = st.countTokens();
				int index = Integer.parseInt(st.nextToken());
				String val = st.nextToken();
				Node n = new Node();
				n.index = index;
				n.value = val;
				
				if(check == 2) {
					nodes[i] = n;
				}else {
					n.left = Integer.parseInt(st.nextToken());
					n.right = Integer.parseInt(st.nextToken());
					nodes[i] = n;
				}
				
			}
			
			int result = cal(nodes[1]);
			
			System.out.println("#"+tc+" "+result);
			
			
			
			

		}
		
	}
	static Node[] nodes;
	static int cal(Node n) {
		if(n.left != 0) {
			if(n.value.equals("+")) {
				return cal(nodes[n.left]) + cal(nodes[n.right]);
			}else if(n.value.equals("-")) {
				return cal(nodes[n.left]) - cal(nodes[n.right]);
			}else if(n.value.equals("*")) {
				return cal(nodes[n.left]) * cal(nodes[n.right]);
			}else {
				return cal(nodes[n.left]) / cal(nodes[n.right]);
			}
		}else {
			return Integer.parseInt(n.value);
		}
	}
	
	
	static class Node {
		int index;
		String value;
		int left = 0;
		int right = 0;
	}

}