[SWEA - Java] 1232. 사칙연산

문제

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

설명

 

위 트리는 식 (9/(6-4))*3을 이진트리로 표현한 것이고 이를 계산한 값을 출력하면 된다.

 

사람들은 사칙 연산을 할때 (9/(6-4))*3식과 같은 중위 표기식으로 계산을 한다.하지만 컴퓨터를 통해 각 연산자의 우선순위대로 계산을 하려면 후위 표기식으로 변환해 계산해야 한다.즉 (9/(6-4))*3 → 964-/3*으로 변환되고 이를 계산한다.

 

따라서 해당 문제에서는 트리를 입력받고 후위 순회하며 각 단계에서 계산을 해주면 된다.

트리에서 후위 표기식 계산 방법

스택을 이용해 계산하면 된다.

 

1. 숫자일 경우 바로 스택에 넣는다.
2. 연산자일 경우 스택에 담긴 두 개의 피연산자를 꺼내 연산 후 다시 스택에 넣는다.

탐색이 종료되면 스택에 남은 최종 값이 연산의 결괏값이 된다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

class Solution {
	static int[][] tree;
	static String[] value;
	static StringBuilder sb;
	static Stack<Double> stack;

	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		sb = new StringBuilder();

		int T = 1;

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

			tree = new int[N+1][2];
			value = new String[N+1];

			for(int i = 1; i <= N; i++) {
				String[] arr = br.readLine().split(" ");
			
				value[i] = arr[1];
				stack = new Stack<>();
				
				if(arr.length == 4) {
					int a = Integer.parseInt(arr[0]);
					int b = Integer.parseInt(arr[2]);
					int c = Integer.parseInt(arr[3]);
					
					tree[a][0] = b;
					tree[a][1] = c;
				}
			}
			
			postOrder(1);
			
			int result = stack.pop().intValue();
			sb.append("#" + test_case + " " + result + "\n");
		}

		System.out.println(sb.toString());
	}
	
	// 후위 순회
	static void postOrder(int x) {
		if(tree[x][0] == 0 && tree[x][1] == 0) {
			 operation(value[x]);
			 System.out.println(value[x]);
		} else {
			if(tree[x][0] != 0) {
				postOrder(tree[x][0]);
			} 
			
			if(tree[x][1] != 0) {
				postOrder(tree[x][1]);
			}

			operation(value[x]);
			System.out.println(value[x]);
		}
	}
	
	static void operation(String v) {
		// 숫자일 경우 
		if(!v.equals("+") && !v.equals("-") && !v.equals("*") && !v.equals("/")) {
			stack.push(Double.parseDouble(v));
			return;
		}
		
		// 연산자일 경우 
		Double b = stack.pop();
		Double a = stack.pop();
		
		if(v.equals("+")) {
			stack.push(a + b);
		} else if(v.equals("-")) {
			stack.push(a - b);
		} else if(v.equals("*")) {
			stack.push(a * b);
		} else if(v.equals("/")) {
			stack.push(a / b);
		}
	}
	
}