Advertisement
Shanix

Untitled

Mar 2nd, 2016
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 6.72 KB | None | 0 0
  1. import java.util.*;
  2.  
  3. public class proj2 {
  4.  
  5. public static String[] pretrav = new String[256];
  6. public static String[] posttrav = new String[256];
  7.  
  8. public static ArrayList<String[]> relationships = new ArrayList<String[]>();
  9.  
  10. public static Node root = null;
  11.  
  12. public static void main(String[] args) {
  13.  
  14. Scanner in = new Scanner(System.in);
  15.  
  16. //Getting user input, to create tree.
  17.  
  18. int relationshipCount = 0;
  19. while(in.hasNextLine()) { //fix
  20. String tempLine = in.nextLine();
  21.  
  22. //Check if we're at the end of input.
  23. if (tempLine.equals("") || tempLine.equals("\n")) {
  24. break;
  25. }
  26.  
  27. //TODO: FIX NEW LINE ERROR
  28.  
  29. //Remove spaces and period from line, they're irrelevant.
  30. tempLine = tempLine.replace(" ", "");
  31. tempLine = tempLine.replace(".", "");
  32. tempLine = tempLine.replace("\n", "");
  33.  
  34. //Actual processing.
  35. if (tempLine.substring(0, 1).equals("<")) {
  36. //Preorder processing.
  37. tempLine = tempLine.replace("<", "");
  38. pretrav = tempLine.split(",");
  39. } else if (tempLine.substring(0, 1).equals(">")) {
  40. //Postorder processing.
  41. tempLine = tempLine.replace(">", "");
  42. posttrav = tempLine.split(",");
  43. } else if (tempLine.substring(0, 1).equals("?")) {
  44. //Relationship processing.
  45. tempLine = tempLine.replace("?", "");
  46. relationships.add(tempLine.split(","));
  47. relationshipCount++;
  48. } else {
  49. //Error handling.
  50. System.out.println("Invalid Input");
  51. System.exit(1);
  52. }
  53. }
  54.  
  55. root = buildTree(posttrav.length, 0, 0);
  56.  
  57. for (int i = 0; i < relationships.size(); i++) {
  58. System.out.println(getRelationship(findNode(relationships.get(i)[0], root), findNode(relationships.get(i)[1], root)));
  59. }
  60.  
  61. }
  62.  
  63. public static Node findNode(String s, Node n) {
  64. if (n.data.equals(s)) {
  65. return n;
  66. } else {
  67. if (n.hasChild()) {
  68. for (int i = 0; i < n.children.size(); i++) {
  69. Node n1 = findNode(s, n.getChild(i));
  70. if (n1 != null) {
  71. return n1;
  72. }
  73. }
  74. } else {
  75. return null;
  76. }
  77. }
  78. return null;
  79. }
  80.  
  81. public static Node buildTree(int size, int prestart, int poststart) {
  82. Node n = new Node(pretrav[prestart]);
  83. prestart++;
  84. int sizeToAdd = 0;
  85. int poststartTemp = poststart;
  86. for (int i = poststart; i < poststart + size - 1; i++) {
  87. if (!(posttrav[i].equals(pretrav[prestart]))) {
  88. sizeToAdd++;
  89. } else {
  90. Node n1 = buildTree(sizeToAdd + 1, prestart, poststartTemp);
  91. n.addGivenNode(n1);
  92. prestart += sizeToAdd + 1;
  93. poststartTemp += sizeToAdd + 1;
  94. sizeToAdd = 0;
  95. }
  96. }
  97. return n;
  98. }
  99.  
  100. public static String getRelationship(Node n1, Node n2) {
  101. if (n1 == null || n2 == null) {
  102. return "Does not exist.";
  103. }
  104.  
  105. int aLength = 0;
  106. int bLength = 0;
  107.  
  108. ArrayList<Node> n1Route = new ArrayList<Node>();
  109. ArrayList<Node> n2Route = new ArrayList<Node>();
  110.  
  111. //Length
  112.  
  113. //Mark all of n1's ancestors
  114. Node n = n1;
  115. while (n != null) {
  116. n1Route.add(n);
  117. n = n.parent;
  118. }
  119.  
  120. n = n2;
  121. while (n != null) {
  122. n2Route.add(n);
  123. n = n.parent;
  124. }
  125.  
  126. n1RouteLoop:
  127. for (int i = 0; i < n1Route.size(); i++) {
  128. for (int j = 0; j < n2Route.size(); j++) {
  129. if (n1Route.get(i).data.equals(n2Route.get(j).data)) {
  130. aLength = i;
  131. bLength = j;
  132. break n1RouteLoop;
  133. }
  134. }
  135. }
  136.  
  137. // System.out.println(aLength + " " + bLength);
  138.  
  139. //Determine relationship
  140. String s = n1.data + " is " + n2.data;
  141. if (aLength == 0) {
  142. if (bLength == 0) {
  143. return s;
  144. } else if (bLength == 1) {
  145. return s + "'s parent.";
  146. } else if (bLength == 2) {
  147. return s + "'s grandparent.";
  148. } else if (bLength == 3) {
  149. return s + "'s great grandparent.";
  150. } else {
  151. s += "'s ";
  152. for (int i = 0; i < bLength - 2; i++) {
  153. s += "great ";
  154. }
  155. s += "grandparent";
  156. return s;
  157. }
  158. } else if (aLength == 1) {
  159. if (bLength == 0) {
  160. return s + "'s child";
  161. } else if (bLength == 1) {
  162. return s + "'s sibling.";
  163. } else if (bLength == 2) {
  164. return s + "'s aunt/uncle.";
  165. } else {
  166. s += "'s ";
  167. for (int i = 0; i < bLength - 2; i++) {
  168. s += "great ";
  169. }
  170. s += "aunt/uncle";
  171. return s;
  172. }
  173. } else if (aLength >= 2) {
  174. if (aLength == 2 && bLength == 0) {
  175. return s + "'s grandchild";
  176. }
  177. if (bLength == 1) {
  178. s += "'s ";
  179. for (int i = 0; i < aLength - 2; i++) {
  180. s += "great ";
  181. }
  182. s += "niece/nephew";
  183. return s;
  184. } else if (bLength >= 2) {
  185. return s + "'s " + (Math.min(bLength, aLength) - 1) + "th cousin " + Math.abs(aLength - bLength) + " times removed.";
  186. }
  187. if (bLength == 0 && aLength >= 3) {
  188. s += "'s ";
  189. for (int i = 0; i < aLength - 2; i++) {
  190. s += "great ";
  191. }
  192. s += "grandchild";
  193. return s;
  194. }
  195. }
  196. return "";
  197. }
  198.  
  199. /* Relationship table.
  200. A’s path length B’s path length Relation of A to B
  201. 0 0 A is B
  202. 0 1 A is B’s parent
  203. 0 2 A is B’s grandparent
  204. 0 3 A is B’s great-grandparent
  205. 0 k > 3 A is B’s (great)^k−2 grandparent
  206.  
  207. 1 0 A is B’s child
  208. 1 1 A is B’s sibling
  209. 1 2 A is B’s aunt/uncle
  210. 1 k ≥ 2 A is B’s (great)^k−2 aunt/uncle
  211.  
  212. 2 0 A is B’s grandchild
  213. k ≥ 2 1 A is B’s (great)^k−2 niece/nephew
  214. k ≥ 2 m ≥ 2 A is B’s (min(m, k) − 1)th cousin |k − m| times removed.
  215.  
  216. k ≥ 3 0 A is B’s (great)^k−2 grandchild*/
  217.  
  218. private static class Node {
  219.  
  220. /** The data. */
  221. public String data;
  222.  
  223. /** Arraylist of children */
  224. public ArrayList<Node> children = new ArrayList<Node>();
  225.  
  226. /** The mark, whether a node has been checked or not. */
  227. public boolean mark;
  228.  
  229. /** Parent node */
  230. public Node parent;
  231.  
  232. /**
  233. * Instantiates sa new node.
  234. * @param s the data
  235. * @param n the parent node
  236. */
  237. public Node(String s, Node n) {
  238. data = s;
  239. mark = false;
  240. parent = n;
  241. }
  242.  
  243. public Node(String s) {
  244. this(s, null);
  245. }
  246.  
  247. /**
  248. * Checks if node has a right child node.
  249. * @return true, if successful
  250. */
  251. public boolean hasChild() {
  252. return !children.isEmpty();
  253. }
  254.  
  255. public void setMark() {
  256. mark = !mark;
  257. }
  258.  
  259. public void addGivenString(String s) {
  260. children.add(new Node(s, this));
  261. }
  262.  
  263. public void addGivenNode(Node n) {
  264. children.add(n);
  265. n.parent = this;
  266. }
  267.  
  268. public String toString() {
  269. return data;
  270. }
  271.  
  272. public Node getChild(int index) {
  273. return children.get(index);
  274. }
  275.  
  276. }
  277.  
  278. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement