[SWEA] JAVA - 1233. 사칙연산유효성검사

노드는 숫자이거나 연산자인 두 가지 경우가 있다.

 

만약 노드가 연산자일때 유효한 경우는

 

1. 왼쪽자식 연산자 + 오른쪽자식 연산자
2. 왼쪽자식 연산자 + 오른쪽자식 숫자
3. 왼쪽자식 숫자 + 오른쪽자식 숫자

 

노드가 숫자일때 유효한 경우는

1. 자식이 있으면 안됀다 (리프 노드여야 한다.)

package com.ssafy.off;

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

public class SWEA_1233_사칙연산유효성검사 {
/**
 * 노드 개수 - N
 * 각줄마다 노드번호, 왼쪽자식 노드번호, 오른쪽자식 노드번호
 * 경현님 코드 보고 이해했습니다 ㅠㅠ
 */
	
	static String[] tree;
	static int N;
	
	private static int dfs(int idx) {
		//리프 노드일때 연산자 아니면 true
		if(idx*2 > N || tree[idx*2] == null) {
			if(!tree[idx].equals("*") && !tree[idx].equals("/") && !tree[idx].equals("-") && !tree[idx].equals("+") && !tree[idx].equals(null)) {
				return 1;
			}else {
				return 0;
			}
			
		}
		//리프 아닌데 숫자면 false
		else if(!tree[idx].equals("*") && !tree[idx].equals("/") && !tree[idx].equals("-") && !tree[idx].equals("+") && !tree[idx].equals(null)) {
			return 0;
		}
		else {
			int left = dfs(idx*2);
			int right = dfs(idx*2+1);
			if(left==1 && right==1) {
				return 1;
			}
		}
		return 0;
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		final int TC = 10;
		for (int t = 1; t <= TC; t++) {
			N = Integer.parseInt(br.readLine());
			tree = new String[N+1];
			int ans = 1;
			for (int i = 1; i <= N; i++) {
				String[] s = br.readLine().split(" ");
				tree[i] = s[1];
			}
			//solve
			ans = dfs(1);
			sb.append("#").append(t).append(" ").append(ans).append("\n");
			
		}// end of test case
		System.out.print(sb);
	}// end of main

}// end of class