1232. [S/W 문제해결 기본] 9일차 - 사칙연산
이진 트리로 표현된 사칙연산 식이 주어진다. 이 식을 계산해서 정수로 출력해라.
(중간 과정의 연산은 실수 연산으로!)
1. post-order
일단 이 문제에서 주어진대로 사칙연산을 하려면 post-order
방식으로 해야한다.
(자식 노드들의 값이 정해지면, 노드의 연산자로 계산)
2. input
-> 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;
}
}