import com sun org apache xpath internal SourceTree import java io Fil

  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
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
import com.sun.org.apache.xpath.internal.SourceTree;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;
/**
* @author Elvira Batyrova
* 11-402
* 22b, 22a
*/
public class SuperBooperTree_Task22 {
public SuperBooperNode_Task22 root;
public SuperBooperTree_Task22() throws FileNotFoundException {
Scanner sc = new Scanner(new File("in.txt"));
root = new SuperBooperNode_Task22(sc.nextLine().substring(0, 1));
}
public static Map<String, ArrayList<String>> getMap() throws FileNotFoundException {
Scanner sc = new Scanner(new File("in.txt"));
Map<String, ArrayList<String>> m = new LinkedHashMap<String, ArrayList<String>>();
while (sc.hasNextLine()) {
String s = sc.nextLine();
int i = s.indexOf(" ");
String key = s.substring(0, i);
String[] a = s.substring(i + 1, s.length()).split("\\|");
ArrayList<String> value = new ArrayList<String>();
for (int j = 0; j < a.length; j++) {
value.add(a[j]);
}
m.put(key, value);
}
sc.close();
return m;
}
public static SuperBooperNode_Task22 getSons(SuperBooperNode_Task22 s) throws FileNotFoundException {
Map<String, ArrayList<String>> m = getMap();
for (Map.Entry<String, ArrayList<String>> entry: m.entrySet()){
if (s.getValue().contains(entry.getKey())) {
ArrayList<String> a = entry.getValue();
for (String x: a) {
SuperBooperNode_Task22 son = new SuperBooperNode_Task22(s.getValue().replace(entry.getKey(), x));
son.setNext(s.getSon());
s.setSon(son);
}
}
}
return s;
}
//Task 22b - строит n слов, принадлежащих языку
public void getWords(int n) throws FileNotFoundException {
Map<String, ArrayList<String>> m = getMap();
Queue<SuperBooperNode_Task22> q = new LinkedList<SuperBooperNode_Task22>();
SuperBooperNode_Task22 p;
q.offer(root);
while(!q.isEmpty() && n > 0) {
p = q.poll();
int k = 0;
for (Map.Entry<String, ArrayList<String>> entry: m.entrySet()){
if (p.getValue().contains(entry.getKey())) {
k++;
}
}
if (k == 0) {
n--;
if (n == 0) {
System.out.println(p.getValue());
}
else {
System.out.print(p.getValue() + ", ");
}
}
else {
if (p.getSon() == null) {
getSons(p);
q.offer(p.getSon());
p = p.getSon();
while (p.getNext() != null) {
q.offer(p.getNext());
p = p.getNext();
}
}
}
}
}
//Task 22a - строит дерево разбора глубины n
public void printTree(int n) throws FileNotFoundException {
Queue<SuperBooperNode_Task22> q = new LinkedList<SuperBooperNode_Task22>();
SuperBooperNode_Task22 p;
q.offer(root);
int level = -1;
while(!q.isEmpty() && n > 0) {
p = q.poll();
if (p.getMark() < n) {
if (p.getMark() > level) {
System.out.println();
System.out.print(p.getValue() + " ");
level++;
}
else {
System.out.print(p.getValue() + " ");
}
}
else {
break;
}
if (p.getSon() == null && p.getNext() == null) {
getSons(p);
}
if (p.getSon() != null) {
q.offer(p.getSon());
p.getSon().setMark(p.getMark() + 1);
p = p.getSon();
while (p.getNext() != null) {
q.offer(p.getNext());
p.getNext().setMark(p.getMark());
p = p.getNext();
}
}
}
}
public static void main(String[] args) throws FileNotFoundException {
SuperBooperTree_Task22 t = new SuperBooperTree_Task22();
System.out.print("Слова, принадлежащие языку: ");
t.getWords(7);
t.printTree(5);
}
}