[SWEA] 1233. [S/W 문제해결 기본] 9일차 - 사칙연산 유효성 검사

문제

사칙연산으로 구성되어 있는 식은 이진 트리로 표현할 수 있다.

아래는 식 “(8/2)*(6-4)”을 이진 트리로 표현한 것이다.

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

 

 
사칙연산 “+, -, *, /”와 양의 정수로만 구성된 임의의 이진 트리가 주어질 때, 이 식의 유효성을 검사하는 프로그램을 작성하여라.

여기서 말하는 유효성이란, 사칙연산 “+, -, *, /”와 양의 정수로 구성된 임의의 식이 적절한 식인지를 확인하는 것으로, 계산이 가능하다면 “1”, 계산이 불가능할 경우 “0”을 출력한다.

(단, 계산이 가능한지가 아닌 유효성을 검사하는 문제이므로 0으로 나누는 경우는 고려하지 않는다. )
 

       

연산이 가능한 경우

연산이 불가능한 경우

                         

[제약 사항]

총 10개의 테스트 케이스가 주어진다.

총 노드의 개수는 200개를 넘어가지 않는다.

트리는 완전 이진 트리 형식으로 주어지며, 노드당 하나의 연산자 또는 숫자만 저장할 수 있다.

노드는 아래 그림과 같은 숫자 번호대로 주어진다.
 

 

풀이방법

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

 

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

 

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

 

이 때, 각 과정에서 연산이 유효한지 검토한다.

 

1) 중위 순회로 방문한 노드가 연산자일 때, 스택에 담겨진 피연산자가 2개 이상인지 확인한다.

 

2) 모든 노드를 방문했을 때, 스택의 크기가 1인지 확인한다.

 

3) 0으로 나누는 경우는 유효하지 않은 식으로 판단하지 않으므로 나누기나 나머지 연산자에서 0으로 나눌 경우 대비한다.

 

각 조건을 만족하는 식이 유효한 식이다. (식의 결과 값자체는 중요하지 않으므로)

 

소스코드

package samsung;

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

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

			System.out.println("#" + t + " " + flag);
		}
	}
}