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

문제

SW Expert Academy

풀이

0. 문제 해석

2022.02.08 - [알고리즘, 자료구조/SWEA] - [SWEA] 1231. 중위순회 (Java)

[SWEA] 1231. 중위순회 (Java)

위 문제와 동일하게 중위 순회를 하면 된다.

 

단, 출력하는 것이 아니고 연산하는 것이기 때문에

자식이 단말 노드일 때, 연산하여 결과값을 저장하는 식으로 중위 순회 하면 해결할 수 있다.

 

위와 같은 트리를 중위 순회 한다면

8 / 3 + 5 * 2 순으로 방문할 것이다.

이때, 자식이 둘다 단말노드 일 때 자신의 연산자로 연산하면 된다.

 

둘다 단말 노드인 경우는 3 + 5 였으므로 그 결과값을 저장해준다.

 

한번 더 진행되면 1 * 2가 남게 되고,

 

결국 결과값이 2가 된다.

 

1. 트리 클래스 메소드 구현, 생성

1231번의 문제와 동일하다.

 

2. 중위 순회 계산

자식이 둘 다 단말 노드 일 때 연산 해준다.

 

3. 전체 코드

// [SWEA] 1232. 사칙연산 (Java)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// 트리 노드
class Node{
	int index;
	String data;
	Node leftNode;
	Node rightNode;
	
	public Node(int index) {
		this.index = index;
		this.data = " ";
		leftNode = null;
		rightNode = null;
	}
}

// 트리 클래스
class Tree{
	Node root = null;
	
	public void add(int index, String data, int leftIndex, int rightIndex) {
		// 트리 최초 생성 시
		if(root == null) {
			root = new Node(index);
			root.data = data;
			if(leftIndex != 0) root.leftNode = new Node(leftIndex);
			if(rightIndex != 0) root.rightNode = new Node(rightIndex);
		}
		else {
			search(root,index,data,leftIndex,rightIndex);
		}
	}
	
	// 이미 존재하는 노드에 연결
	public void search(Node root, int index, String data, int leftIndex, int rightIndex) {	
		// 찾았을 때 좌우 연결
		if(root.index == index) {
			root.data = data;
			if(leftIndex != 0) root.leftNode = new Node(leftIndex);
			if(rightIndex != 0) root.rightNode = new Node(rightIndex);
		}
		
		// 못 찾으면 좌우 탐색
		else {
			if(root.leftNode != null) search(root.leftNode,index,data,leftIndex,rightIndex);
			if(root.rightNode != null) search(root.rightNode,index,data,leftIndex,rightIndex);
		}
	}
	
	// 중위 순회 (왼쪽 자식, 루트, 오른쪽 자식)
	public double inOrder(Node root) {
		String curData = root.data;
		double left = 0;
		double right = 0;
		double result = 0;
		
		// left 결정 (마지막 레벨에 있는 숫자부터 연산)
		if(root.leftNode.leftNode == null) {
			left = Double.parseDouble(root.leftNode.data);
		}
		else {
			left = inOrder(root.leftNode);
		}
		
		// right 결정 (마지막 레벨에 있는 숫자부터 연산)
		if(root.rightNode.rightNode == null) {
			right = Double.parseDouble(root.rightNode.data);
		}
		else {
			right = inOrder(root.rightNode);
		}

		// 연산
		if(curData.equals("+")) {
			result = left + right;
		}
		else if(curData.equals("-")) {
			result = left - right;
		}
		else if(curData.equals("*")) {
			result = left * right;
		}
		else if(curData.equals("/")) {
			result = left / right;
		}
		return result;
	}
}

public class Solution {
	static int n; // 정점의 총 수
	static Tree tree; // 트리
	
 public static void main(String[] args) throws IOException{
 	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 	
 	for(int t = 1; t <= 10; t++) {
 		n = Integer.parseInt(br.readLine()); 	
		tree = new Tree();
		
 		for(int i = 1; i <= n; i++) {
 			StringTokenizer st = new StringTokenizer(br.readLine());
 			st.nextToken();
 			String data = st.nextToken();
 			int leftIndex = 0;
 			int rightIndex = 0;
 			
 			if (st.countTokens() == 2) {
 				leftIndex = Integer.parseInt(st.nextToken());
 				rightIndex = Integer.parseInt(st.nextToken());
 			}
 			
 			tree.add(i, data, leftIndex, rightIndex);
 		}
 		
 		System.out.println("#" + t + " " + (int)tree.inOrder(tree.root));
 	}
  }
}