SWEA 1233 사칙연산 유효성 검사

[SWEA D4 1233 사칙연산 유효성 검사]

완전이진트리 문제이다.

수식이 성립되려면 숫자 사이에 무조건 연산자가 있어야 한다. 8*2 이렇게. 그러면 단말 노드(리프노드)는 무조건 숫자여야 하고, 연산자 노드는 무조건  자식 노드(왼, 오)가 둘 다 있어야 한다.

처음엔 dfs로 중위순회해서 8/2*6-4 이런 순서로 전부 노드를 검사해야하나 싶었다.그런데 문제를 풀다 보니 입력이 주어질 때 [노드 번호 노드정보 왼노드 오른노드] 이렇게 주어지는게 아닌가?

그럼 그냥 입력받으면서 현재 노드가 숫자인데 뒤에 자식 노드 정보가 있는지, 연산자인데 뒤에 자식 노드가 없는지 두 가지만 체크해주면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * 사칙연산 유효성 검사 
 * */

public class Solution{
	static int N;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		for(int tc=1; tc<=10; tc++) {
			int N = Integer.parseInt(in.readLine());
			boolean flag = true;
			StringTokenizer st;
			
			for(int i=0; i<N; i++) {
				st = new StringTokenizer(in.readLine(), " ");
				st.nextToken();
				
                // flag를 설정해줘서 이미 안되는 수식이면 건너뛴다.
				if(!flag)	continue;
				String node = st.nextToken();	
				
                // 현재 노드가 연산자일 때 뒤에 자식 노드 정보가 더 있는지 체크. 있으면 수식성립 안됨
				if(node.equals("+") || node.equals("-") || node.equals("*") || node.equals("/")) {
					if(!st.hasMoreTokens())
						flag = false;
				}else {
                   // 현재 노드가 숫자일 땐 뒤에 자식 노드가 있으면 안됨.
					if(st.hasMoreTokens())
						flag = false;
				}
			}
			System.out.printf("#%d %d\n", tc, flag ? 1 : 0);
		}

	}

}