[SWEA] 1232. [S/W 문제해결 기본] 9일차 - 사칙연산

문제

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

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

 

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

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

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

 

풀이방법

DFS(깊이 우선 탐색) 알고리즘으로 후위 순회를 하면서 

 

노드의 값이 피연산자이면 스택에 담고

 

연산자이면 스택에 담겨진 두개의 피연산자를 뽑아 연산 후 다시 스택에 담는다.

 

탐색을 종료하고 스택에 남은 최종 값이 연산의 결과가 된다.

 

소스코드

package samsung;

import java.io.*;
import java.util.*;

public class s_1232 {
	static String[] vertex;
	static int[][] edge;
	static int n;
	static int[] visit;
	static Stack <Integer> nums;
	
	public static void op(String s) {
		if(s.equals("+")) {
			int a = nums.pop();
			int b = nums.pop();
			nums.push(b+a);
		}
		else if(s.equals("-")) {
			int a = nums.pop();
			int b = nums.pop();
			nums.push(b-a);
		}
		else if(s.equals("*")) {
			int a = nums.pop();
			int b = nums.pop();
			nums.push(b*a);
		}
		else if(s.equals("/")) {
			int a = nums.pop();
			int b = nums.pop();
			nums.push(b/a);
		}
		else {
			int num = Integer.parseInt(s);
			nums.push(num);
		}
	}
	
	public static void dfs(int x) {
		visit[x] = 1;
		
		for(int i = 1; i <= n; i++) {
			if(edge[x][i] == 1 && visit[i] == 0)
				dfs(i);
		}
		op(vertex[x]);
	}
	
	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());
			edge = new int[n + 1][n + 1];
			vertex = new String[n+1];
			visit = new int[n + 1];
			nums = new Stack<>();
			
			for(int i = 0; i < n; i++) {
				StringTokenizer tk = new StringTokenizer(br.readLine());
				int from = Integer.parseInt(tk.nextToken());
				vertex[from] = tk.nextToken(); 
				
				for(int j = 0; j < 2; j++) {
					if(tk.hasMoreTokens()) {
						int to = Integer.parseInt(tk.nextToken());
						edge[from][to] = 1;
					}
				}
			}
			dfs(1);
			System.out.println("#" + t + " " + nums.pop());
		}
	}
}