Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- public class proj2 {
- public static String[] pretrav = new String[256];
- public static String[] posttrav = new String[256];
- public static ArrayList<String[]> relationships = new ArrayList<String[]>();
- public static Node root = null;
- public static void main(String[] args) {
- Scanner in = new Scanner(System.in);
- //Getting user input, to create tree.
- int relationshipCount = 0;
- while(in.hasNextLine()) { //fix
- String tempLine = in.nextLine();
- //Check if we're at the end of input.
- if (tempLine.equals("") || tempLine.equals("\n")) {
- break;
- }
- //TODO: FIX NEW LINE ERROR
- //Remove spaces and period from line, they're irrelevant.
- tempLine = tempLine.replace(" ", "");
- tempLine = tempLine.replace(".", "");
- tempLine = tempLine.replace("\n", "");
- //Actual processing.
- if (tempLine.substring(0, 1).equals("<")) {
- //Preorder processing.
- tempLine = tempLine.replace("<", "");
- pretrav = tempLine.split(",");
- } else if (tempLine.substring(0, 1).equals(">")) {
- //Postorder processing.
- tempLine = tempLine.replace(">", "");
- posttrav = tempLine.split(",");
- } else if (tempLine.substring(0, 1).equals("?")) {
- //Relationship processing.
- tempLine = tempLine.replace("?", "");
- relationships.add(tempLine.split(","));
- relationshipCount++;
- } else {
- //Error handling.
- System.out.println("Invalid Input");
- System.exit(1);
- }
- }
- root = buildTree(posttrav.length, 0, 0);
- for (int i = 0; i < relationships.size(); i++) {
- System.out.println(getRelationship(findNode(relationships.get(i)[0], root), findNode(relationships.get(i)[1], root)));
- }
- }
- public static Node findNode(String s, Node n) {
- if (n.data.equals(s)) {
- return n;
- } else {
- if (n.hasChild()) {
- for (int i = 0; i < n.children.size(); i++) {
- Node n1 = findNode(s, n.getChild(i));
- if (n1 != null) {
- return n1;
- }
- }
- } else {
- return null;
- }
- }
- return null;
- }
- public static Node buildTree(int size, int prestart, int poststart) {
- Node n = new Node(pretrav[prestart]);
- prestart++;
- int sizeToAdd = 0;
- int poststartTemp = poststart;
- for (int i = poststart; i < poststart + size - 1; i++) {
- if (!(posttrav[i].equals(pretrav[prestart]))) {
- sizeToAdd++;
- } else {
- Node n1 = buildTree(sizeToAdd + 1, prestart, poststartTemp);
- n.addGivenNode(n1);
- prestart += sizeToAdd + 1;
- poststartTemp += sizeToAdd + 1;
- sizeToAdd = 0;
- }
- }
- return n;
- }
- public static String getRelationship(Node n1, Node n2) {
- if (n1 == null || n2 == null) {
- return "Does not exist.";
- }
- int aLength = 0;
- int bLength = 0;
- ArrayList<Node> n1Route = new ArrayList<Node>();
- ArrayList<Node> n2Route = new ArrayList<Node>();
- //Length
- //Mark all of n1's ancestors
- Node n = n1;
- while (n != null) {
- n1Route.add(n);
- n = n.parent;
- }
- n = n2;
- while (n != null) {
- n2Route.add(n);
- n = n.parent;
- }
- n1RouteLoop:
- for (int i = 0; i < n1Route.size(); i++) {
- for (int j = 0; j < n2Route.size(); j++) {
- if (n1Route.get(i).data.equals(n2Route.get(j).data)) {
- aLength = i;
- bLength = j;
- break n1RouteLoop;
- }
- }
- }
- // System.out.println(aLength + " " + bLength);
- //Determine relationship
- String s = n1.data + " is " + n2.data;
- if (aLength == 0) {
- if (bLength == 0) {
- return s;
- } else if (bLength == 1) {
- return s + "'s parent.";
- } else if (bLength == 2) {
- return s + "'s grandparent.";
- } else if (bLength == 3) {
- return s + "'s great grandparent.";
- } else {
- s += "'s ";
- for (int i = 0; i < bLength - 2; i++) {
- s += "great ";
- }
- s += "grandparent";
- return s;
- }
- } else if (aLength == 1) {
- if (bLength == 0) {
- return s + "'s child";
- } else if (bLength == 1) {
- return s + "'s sibling.";
- } else if (bLength == 2) {
- return s + "'s aunt/uncle.";
- } else {
- s += "'s ";
- for (int i = 0; i < bLength - 2; i++) {
- s += "great ";
- }
- s += "aunt/uncle";
- return s;
- }
- } else if (aLength >= 2) {
- if (aLength == 2 && bLength == 0) {
- return s + "'s grandchild";
- }
- if (bLength == 1) {
- s += "'s ";
- for (int i = 0; i < aLength - 2; i++) {
- s += "great ";
- }
- s += "niece/nephew";
- return s;
- } else if (bLength >= 2) {
- return s + "'s " + (Math.min(bLength, aLength) - 1) + "th cousin " + Math.abs(aLength - bLength) + " times removed.";
- }
- if (bLength == 0 && aLength >= 3) {
- s += "'s ";
- for (int i = 0; i < aLength - 2; i++) {
- s += "great ";
- }
- s += "grandchild";
- return s;
- }
- }
- return "";
- }
- /* Relationship table.
- A’s path length B’s path length Relation of A to B
- 0 0 A is B
- 0 1 A is B’s parent
- 0 2 A is B’s grandparent
- 0 3 A is B’s great-grandparent
- 0 k > 3 A is B’s (great)^k−2 grandparent
- 1 0 A is B’s child
- 1 1 A is B’s sibling
- 1 2 A is B’s aunt/uncle
- 1 k ≥ 2 A is B’s (great)^k−2 aunt/uncle
- 2 0 A is B’s grandchild
- k ≥ 2 1 A is B’s (great)^k−2 niece/nephew
- k ≥ 2 m ≥ 2 A is B’s (min(m, k) − 1)th cousin |k − m| times removed.
- k ≥ 3 0 A is B’s (great)^k−2 grandchild*/
- private static class Node {
- /** The data. */
- public String data;
- /** Arraylist of children */
- public ArrayList<Node> children = new ArrayList<Node>();
- /** The mark, whether a node has been checked or not. */
- public boolean mark;
- /** Parent node */
- public Node parent;
- /**
- * Instantiates sa new node.
- * @param s the data
- * @param n the parent node
- */
- public Node(String s, Node n) {
- data = s;
- mark = false;
- parent = n;
- }
- public Node(String s) {
- this(s, null);
- }
- /**
- * Checks if node has a right child node.
- * @return true, if successful
- */
- public boolean hasChild() {
- return !children.isEmpty();
- }
- public void setMark() {
- mark = !mark;
- }
- public void addGivenString(String s) {
- children.add(new Node(s, this));
- }
- public void addGivenNode(Node n) {
- children.add(n);
- n.parent = this;
- }
- public String toString() {
- return data;
- }
- public Node getChild(int index) {
- return children.get(index);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement