[SWEA] #1232 - 사칙연산

※ 문제에 대한 저작권은 SW Expert Academy에 있습니다.

💡 출처

---

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

SW Expert Academy

 

💡 문제

---

[설명]

사칙연산으로 구성되어 있는 식은 이진트리로 표현할 수 있다. 아래는 식 “(9/(6-4))*3”을 이진트리로 표현한 것이다.

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

 

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

단, 중간 과정에서의 연산은 실수 연산으로 하되, 최종 결괏값이 정수로 떨어지지 않으면 정수부만 출력한다.

위의 예에서는 최종 결괏값이 13.5이므로 13을 출력하면 된다.

 

[제약 사항]

정점의 총 수 N은 1≤N≤1000

 

💡 아이디어

---

우선 Tree를  Class로 만들어 관리하도록 했다.

연산자가 들어오면 피연산자 2개도 같이 들어오기 때문에 Tree에 추가해준다.

연산자가 아니라면 Tree에 단순히 노드를 추가해준다.

Tree에 모든 것을 넣었다면 재귀를 이용해 문제를 해결할 수 있다.

우선 연산자가 나온다면 왼쪽 피연산자와 오른쪽 피연산자를 이용해 계산을 해야 하는데

왼쪽이나 오른쪽 피연산자의 경우 아래의 노드가 더 있다면 결과가 달라질 수 있다. 

그렇기 때문에 왼쪽 노드로 계속 뻗어 나가 결과를 계산하고, 오른쪽 노드로 계속 뻗어 나가 결과를 계산하는 과정을

재귀로 반복하면 최종적인 결과를 얻을 수 있다.

 

💡 소스코드

---

package SWEA;

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

class Node {//노드 클래스
	float data;
	int lchild;
	int rchild;
	char op;
}

public class SWEA_P1232_사칙연산 {

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("./SWEA_INPUT/SWEA_P1232_input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		for (int TC = 1; TC <= 10; TC++) {
			int T = Integer.parseInt(br.readLine());

			Node[] Tree = new Node[T + 1];//Node타입의 배열 선언

			for (int i = 0; i <= T; i++)
				Tree[i] = new Node();//각 Node 생성

			for (int i = 0; i < T; i++) {
				StringTokenizer sz = new StringTokenizer(br.readLine());

				int idx = Integer.parseInt(sz.nextToken());//인덱스 번호
				String s = sz.nextToken();

				if (!Character.isDigit(s.charAt(0))) {//만약 연산자가 들어오면
					Tree[idx].op = s.charAt(0);//연산자를 넣고
					Tree[idx].lchild = Integer.parseInt(sz.nextToken());
					Tree[idx].rchild = Integer.parseInt(sz.nextToken());
					//왼쪽, 오른쪽 자식도 넣음
				}

				else
					Tree[idx].data = Float.parseFloat(s);//연산자가 아닌 숫자가 들어오면 data에 저장
			}

			System.out.println("#" + TC + " " + (int) solve(Tree, 1));
		}
		br.close();
	}

	public static float result;

	public static float solve(Node[] Tree, int node) {
		if (Tree[node].op != '0' && Tree[node].op == '+')
			result = solve(Tree, Tree[node].lchild) + solve(Tree, Tree[node].rchild);

		else if (Tree[node].op != '0' && Tree[node].op == '-')
			result = solve(Tree, Tree[node].lchild) - solve(Tree, Tree[node].rchild);

		else if (Tree[node].op != '0' && Tree[node].op == '*')
			result = solve(Tree, Tree[node].lchild) * solve(Tree, Tree[node].rchild);

		else if (Tree[node].op != '0' && Tree[node].op == '/')
			result = solve(Tree, Tree[node].lchild) / solve(Tree, Tree[node].rchild);	
		//현재 노드가 연산자이면 (왼쪽 자식 연산자 오른쪽 자식)의 형태로 재귀

		else//연산자가 아니면 result에 넣고
			result = Tree[node].data;

		return result;//return
	}
}

 

💡 결과

---