[SWEA] 1232. 사칙연산 (JAVA)

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

SW Expert Academy

[문제]

사칙연산으로 구성되어 있는 식은 이진 트리로 표현할 수 있다. 아래는 식 “(9/(6-4))*3”을 이진 트리로 표현한 것이다.
임의의 정점에 연산자가 있으면 해당 연산자의 왼쪽 서브 트리의 결과와 오른쪽 서브 트리의 결과를 사용해서 해당 연산자를 적용한다.

사칙연산 “+, -, *, /”와 양의 정수로만 구성된 임의의 이진트리가 주어질 때, 이를 계산한 결과를 출력하는 프로그램을 작성하라.
단, 중간 과정에서의 연산은 실수 연산으로 하되, 최종 결과값이 정수로 떨어지지 않으면 정수부만 출력한다.
위의 예에서는 최종 결과값이 13.5이므로 13을 출력하면 된다.

 

[풀이]

이진 트리 후위순회를 통해 후위표기식으로 접근하며, 노드값이 숫자일 때는 stack에 넣고, 노드값이 연산자일 때는 스택에서 숫자를 빼내어 연산 후 다시 집어넣어주는 방식으로 문제를 해결하였다.

package A0208;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class SWEA_사칙연산 {

	static int N;
	static int[][] tree;
	static String[] value;
	static Stack<Double> stack;
	
	public static void postOrder(int idx) {
		 
		if(idx!=0) {
			postOrder(tree[idx][0]);
			postOrder(tree[idx][1]);
			if(isOperator(value[idx])) { //노드 값이 연산자라면
				calculate(value[idx]); //연산 수행
			}
			else stack.push(Double.parseDouble(value[idx])); //연산자가 아니라면 stack에 push
		}
		
	}
	public static void calculate(String c) {
		
		double y = stack.pop();
		double x = stack.pop();
		if(c.equals("+")) {
			stack.push(x+y);
		}
		else if(c.equals("-")) {
			stack.push(x-y);
		}
		else if(c.equals("*")) {
			stack.push(x*y);
		}
		else if(c.equals("/")) {
			stack.push(x/y);
		}
	}
	private static boolean isOperator(String c) {
	       if (c.equals("+")|| c.equals("-") || c.equals("*") || c.equals("/"))
	    	   return true;
	       return false;
	 }
	
	public static void main(String[] args) throws Exception {
		//System.setIn(new FileInputStream("input_cal3.txt")); 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = 10;

		for(int test_case = 1; test_case <= T; test_case++) {
			
			N = Integer.parseInt(br.readLine());
			tree = new int[N+1][2];
			value = new String[N+1]; //트리노드에 저장되는 값
			stack= new Stack<Double>();
			
			for(int i=1;i<=N;i++) {
				String[] tmp = br.readLine().split(" ");
				if(tmp.length==4) {
					int left = Integer.parseInt(tmp[2]);
					int right = Integer.parseInt(tmp[3]);
					tree[i][0]=left;
					tree[i][1]=right;
				}
				value[i]=tmp[1];
			
			}
			postOrder(1);
			int answer = Integer.parseInt(String.valueOf(Math.round(stack.pop()))); //결과값은 정수부만 출력
			System.out.println("#"+test_case+" "+answer);
	}
}
}

[소감]

이번 문제도 역시나 입력을 트리로 구현하는 부분이 가장 어려웠다. 배열을 이용해서 트리를 구현하게 되면 메모리 낭비가 심하다고 한 것 같은데.. 지금은 배열도 벅차다. 배열이 익숙해지면 리스트를 사용해보아야겠다.