[SWEA] 1233.四則演算の検証(d 4)

質問する

四則演算で構成される式はバイナリツリーで表すことができる.
式「(8/2)*(6-4)」のツリーを次に示します.
任意の頂点に演算子がある場合は、演算子の左側のサブツリーの結果と右側のサブツリーの結果を使用して演算子を適用します.

「+、-、*、/」および正の整数からなる任意のバイナリツリーが与えられた場合、この式を検証するプログラムを作成します.
ここでいう有効性は、4つの演算「+,-,*,/」と正の整数からなる任意の式が正しいかどうかをチェックし、できれば「1」を出力し、できない場合は「0」を出力することです.
(ただし、これは検証問題であり、0に分けることは考えられません.)

[制限]

合計10件のテストケースがあります.
ノードの合計数は200を超えません.
ツリーは完全なバイナリツリーとして与えられ、各ノードには1つの演算子または数値しか格納されません.
ノードは、下図に示す数字番号で与えられます.

[入力]

各テストケースの最初の行は、各ケースツリーの頂点総数N(1≦N≦200)を与える.
そして、N行に各頂点の情報が与えられる.
頂点に関する情報は、頂点のアルファベット、頂点の左サブノード、右サブノードの頂点番号の順に与えられます.
頂点番号は1～Nの整数で区切られます.入力中の頂点番号のルールは、ルート頂点番号が1である必要があります.
入力した隣接する数値または演算子、サブ頂点の番号は、スペースで区切られています.
上記の例では、数字8が4番の頂点に対応する場合は「4 8」、演算子「/」が2番の頂点に対応する場合は、2つのサブノードはそれぞれ数字「8」の4番の頂点と数字「2」の5番の頂点であるため、「2/45」が与えられる.
合計10件のテストケースがあります.

[出力]

#コードとともにテスト用例の番号を出力し、スペースを空けてテスト用例の正解を出力します.
入力
171
1 - 2 3
2 - 4 5
3 + 6 7
4/8 9
5 - 10 11
6 + 12 13
7 - 14 15
8 - 16 17
9 18 19
10 7 20 21
11 22 23
12 - 24 25
13 26 27
14/28 29
15 + 30 31
16 - 32 33
17/34 35
18 36 37
19 38 39
20 3 40 41
21 + 42 43
22 - 44 45
23/46 47
24 48 49
25 50 51
26/52 53
27 - 54 55
28 - 56 57
29 + 58 59
30/60 61
31/62 63
32 64 65
33/66 67
34/68 69
35 - 70 71
36/72 73
37 + 74 75
38 - 76 77
39 78 79
40 + 80 81
41 2 82 83
42 84 85
43/86 87
44 - 88 89
45 - 90 91
46 - 92 93
47 94 95
48/96 97
49 98 99
50 + 100 101
51 102 103
52 + 104 105
53 106 107
54/108 109
55 110 111
56 - 112 113
57/114 115
58 116 117
59 - 118 119
60 120 121
61 122 123
62 124 125
63 126 127
64 + 128 129
65 - 130 131
........

しゅつりょく

#1 0
#2 0
.......

に答える

質問のタイプ:ツリー
有効な式の条件
1.ノード値:2つの演算子->サブノード(2つの演算子であるため)が必要です.
2.ノード値:数値->終端ノード(数値では演算できないため)

コード#コード#

①BufferedRearの使用

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

public class Solution_d4_1233_사칙연산유효성검사_대전_5반_이주희 {

	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("res/input_d4_1233.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		for(int tc = 1; tc<=10; tc++) {
			int N = Integer.parseInt(new StringTokenizer(br.readLine()).nextToken());		// 총 노드의 개수
			int res = 1;
			
			StringTokenizer st;
			for(int i=0; i<N; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				if(res==0) continue;
				
				st.nextToken(); 					// 노드 번호 버림
				char ch = st.nextToken().charAt(0);	//노드의 값
				
				if(ch=='+' || ch == '-' || ch == '*' || ch == '/') { // 자식노드가 2개 있어야 함
					if(st.hasMoreTokens()) {						// 왼쪽 자식노드 존재 여부
						st.nextToken();
					}
					else {	 // 없다면
						res = 0; continue;
					}
					if(st.hasMoreTokens()) {			// 오른쪽 자식노드 존재 여부
						st.nextToken();
					}
					else {
						res = 0;
					}
				} else {	// 단말노드여야 함.
					if(st.hasMoreTokens()) {
						res = 0;
					}
				}
			}
			sb.append("#").append(tc).append(" ").append(res).append("\n");
		}
		
		System.out.print(sb.toString());
		br.close();
	}

}

②スキャナー使用

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

public class Solution_d4_1233_사칙연산유효성검사_대전_5반_이주희2 {

	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("res/input_d4_1233.txt"));
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		
		for(int tc = 1; tc<=10; tc++) {
			int N = Integer.parseInt(sc.nextLine());
			
			int res = 1;
			for(int i=0; i<N; i++) {
				String[] sa = sc.nextLine().split(" ");
				if(res==0) continue;
				
				char op = sa[1].charAt(0);
			
				if(op>='0' && op<='9') {
					if(sa.length > 2) res=0; 
				}
				else {
					if(sa.length < 4) res=0;
				}
			}
			
			sb.append("#").append(tc).append(" ").append(res).append("\n");
		}
		
		System.out.print(sb.toString());
		sc.close();
	}

}