/
Mod3DFATable.java
80 lines (68 loc) · 2.16 KB
/
Mod3DFATable.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package org.vkedco.toc.dfa;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
*
* @author Vladimir Kulyukin
*/
public class Mod3DFATable {
static final int Q0 = 0;
static final int Q1 = 1;
static final int Q2 = 2;
static final int Q3 = 3;
private static int mCurrState;
static int[][] deltaTable =
{
{Q0, Q1}, // state Q0: delta('0', Q0) = Q0; delta('1', Q1)
{Q2, Q0}, // state Q1: delta('0', Q1) = Q2; detal('1', Q0)
{Q1, Q2}, // state Q2: delta('0', Q2) = Q1; delta('1', Q2)
{Q3, Q3} // state Q3: delta('0', Q3) = Q3; delta('1', Q3)
};
static void reset() {
mCurrState = Q0;
}
static void process(String input) {
for(int i = 0; i < input.length(); i++) {
char c = input.charAt(i);
try {
// This is based on the following Java trick:
// System.out.println('1'-'0'); // this outputs 1
// System.out.println('1'-'1'); // this outputs 0
mCurrState = deltaTable[mCurrState][c-'0'];
}
catch ( ArrayIndexOutOfBoundsException ex ) {
mCurrState = Q3;
}
}
}
static boolean isAccepted() {
return mCurrState == Q0;
}
static void mod3StringFilter() {
try {
BufferedReader input =
new BufferedReader(new InputStreamReader(System.in));
String inputStr = input.readLine();
while ( inputStr != null ) {
Mod3DFA.reset();
Mod3DFA.process(inputStr);
if ( Mod3DFA.isAccepted() )
System.out.println("YES");
else
System.out.println("NO");
inputStr = input.readLine();
}
}
catch ( IOException ex ) {
System.err.println(ex.toString());
}
}
public static void main(String[] argv) {
Mod3DFATable.mod3StringFilter();
}
}