[SWEA] 1232. 사칙연산

문제

1232. [S/W 문제해결 기본] 9일차 - 사칙연산
이진 트리로 표현된 사칙연산 식이 주어진다. 이 식을 계산해서 정수로 출력해라.
(중간 과정의 연산은 실수 연산으로!)

풀이

1. post-order
일단 이 문제에서 주어진대로 사칙연산을 하려면 post-order 방식으로 해야한다.
(자식 노드들의 값이 정해지면, 노드의 연산자로 계산)

2. input

• 2번째 입력 데이터가 숫자이면, 단말노드이므로 더 이상 받지 않고 다음 줄로 넘어간다.
• 2번째 입력 데이터가 연산자이면, 연산할 숫자가 담긴 자식노드 2개를 추가로 입력받는다.

-> isDigit(char t) 라는 함수를 만들어서 2번째 입력 데이터를 식별했다.

배열이름	저장된 정보
tree[][]	트리정보 저장(부모-자식)
num[]	노드의 숫자값 저장 (연산자는 저장X -> 0으로 남아있음)
oper[]	연산자 저장 (숫자는 저장X)

static void input(int [][] tree, double [] num, char [] oper, int N, Scanner sc) {
	int a;
	String b;
	int i;
	
	for (i=1; i<=N; i++) {
		a = sc.nextInt();
		b = sc.next();
        
        	// isDigit(char t) : t가 연산자이면 false 반환하게 만든 함수
		if (!isDigit(b.charAt(0))) {
			oper[i] = b.charAt(0);
			tree[i][0] = sc.nextInt();
			tree[i][1] = sc.nextInt();
		} else {
			num[i] = Double.parseDouble(b);
		}
	}
}

3. 연산하기
1. 현재 n번 노드에 있다면, oper[n]이 연산자인지 확인하고, 연산자가 아니라면 num[n]을 반환한다. (숫자)
2. 연산자라면, 두 자식 노드의 값을 받아온다. (double)
3. oper[n]의 연산자 종류에 맞춰 계산하여 반환한다. (하드코딩이라 슬프다.)

자바코드

import java.util.Scanner;
import java.io.FileInputStream;

class Solution
{	
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		int T = 10;
		for(int test_case = 1; test_case <= T; test_case++)
		{
			int N = sc.nextInt();
			int [][] tree = new int[N+1][2]; // 1 left 2 right
			char [] oper = new char[N+1]; // save operator
			double [] num = new double[N+1]; // value of Node
			input(tree, num, oper, N, sc);
			
			System.out.printf("#%d %d\n", test_case, (int)calculate(tree, num, oper, 1));
		}
	}
	
	static double calculate(int [][] tree, double [] num, char [] oper, int cur) {
		if (isDigit(oper[cur])) return num[cur];
		
		double a = child(tree, num, oper, 0, cur);
		double b = child(tree, num, oper, 1, cur);
		
		if (oper[cur] == '/') return a/b;
		else if (oper[cur] == '*') return a*b;
		else if (oper[cur] == '+') return a+b;
		else return a-b;
	}
	
	static double child(int [][] tree, double [] num, char [] oper, int flag, int cur) {
		if (tree[cur][flag] == 0) return 1;
		return calculate(tree, num, oper, tree[cur][flag]);
	}
	
	static void input(int [][] tree, double [] num, char [] oper, int N, Scanner sc) {
		int a;
		String b;
		int i;
		
		for (i=1; i<=N; i++) {
			a = sc.nextInt();
			b = sc.next();
			if (!isDigit(b.charAt(0))) {
				oper[i] = b.charAt(0);
				tree[i][0] = sc.nextInt();
				tree[i][1] = sc.nextInt();
			} else {
				num[i] = Double.parseDouble(b);
			}
		}
	}
	
	static boolean isDigit(char t) {
		if (t=='/' || t=='+'||t=='-'||t=='*') return false;
		return true;
	}
}