leetcode/prob8.java at master · ketankokane94/leetcode · GitHub

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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
// Given a valid XML document, read it in a tree structure.

// <html>
//   <body>
//     <div>
//       <h1>CodeRust</h1>
//       <a>http://coderust.com</a>
//     </div>
//     <div>
//         <h2>Chapter 1</h2>
//     </div>
//     <div>
//         <h3>Chapter 2</h3>
//         <h4>Chapter 2.1</h4>
//     </div>
//   </body>
// </html>

/*
use of stack to match the latest closing tag,
tokenize the string, somehow
  * generate_tree
    ** for every token
      *** if opening token -
      create a node
      while corresponding closing tag is not meet
      call generate_tree and assign the tree generated by it as its child, its going to be an n-ary tree
      *** elseif closing node return null
      *** else create a node and simply return
*/

import java.util.*;

class TreeNode{
  String text;
  ArrayList<TreeNode> children;

  public TreeNode(String val, ArrayList<TreeNode> list){
    this.text = val;
    this.children = list;
  }

  public void addChild(TreeNode child){
    this.children.add(child);
  }
}

public class prob8{
  static HashMap <String, String> map;
  static HashSet<String> openingTags ;
  static HashSet<String> closingTags ;

  public static void main(String[] args) {
    System.out.println("XML to tree");
    map = new HashMap<>();
    map.put("<html>", "<//html>");
    map.put("<body>", "<//body>");
    map.put("<h1>", "<//h1>");
    map.put("<h2>", "<//h2>");
    map.put("<h3>", "<//h3>");
    map.put("<h4>", "<//h4>");
    map.put("<h5>", "<//h5>");
    map.put("<div>", "<//div>");
    map.put("<a>", "<//a>");

    openingTags = new HashSet<>();
    for (String key :map.keySet() ) {
          openingTags.add(key);
    }
    // because could not fnd an easy way to get values of map in a set,
    // could be because values need not to be unique. hence list and not set by default, which is the case for key, as they are for sure Unique
    closingTags = new HashSet<>();
    for (String val: map.values()){
        closingTags.add(val);
    }
    testCase1();
  }

  public static void testCase1(){
    String XMLStr = "<html><body><div><h1>CodeRust<//h1><a>http://coderust.com<//a><//div><div><h2>Chapter 1<//h2><//div><div><h3>Chapter 2<//h3><h4>Chapter 2.1<//h4><//div><//body><//html>";
    LinkedList<String> tokens = tokenize(XMLStr);
    TreeNode root = generateTree(tokens, new Stack<String>());
    printTree(root, 0);
    for (String str : tokens ) {
      System.out.println(str);
    }
  }


  static LinkedList<String> tokenize(String XMLStr){
    // O(n) function
    LinkedList<String> tokens = new LinkedList<>();

    // ArrayList<String> tokens = new ArrayList<>();
    char[] chars = XMLStr.toCharArray();
    StringBuilder sb = new StringBuilder();
    int start = 0;
    for(int end = 0 ; end < XMLStr.length(); end++){
      if(chars[end]== '>' || chars[end] == '<'){
        if (chars[end]== '>'){
          start = end + 1;
          sb.append('>');
          tokens.add(sb.toString());
          // tokens.add(s)
          sb.setLength(0);
        }
        else{
          if (sb.length()> 0)
            tokens.add(sb.toString());
          sb.setLength(0);
          sb.append('<');
        }
      }
      else{
        sb.append(chars[end]);
      }
    }
    return tokens;
  }

  private static boolean isOpeningTag(String token){
    return openingTags.contains(token);
  }

  private static boolean isClosingTag(String token){
    return closingTags.contains(token);
  }


  private static TreeNode generateTree(LinkedList<String> tokens, Stack<String> stack){

      String token = tokens.removeFirst();
      if(isOpeningTag(token)){
          stack.push(map.get(token));
          TreeNode root  = new TreeNode(token, new ArrayList<TreeNode>() );
          while(!stack.peek().equals(token)){
            token = tokens.getFirst();
            root.addChild(generateTree(tokens, stack));
          }
          stack.pop();
          return root;
      }
      else if (!isClosingTag(token)){
          return new TreeNode(token, new ArrayList<TreeNode>());
      }
      return null;
  }

  private static void printTree(TreeNode root, int depth) {
    if (root == null) {
      return;
    }
    for (int i = 0; i < depth; ++i)
      System.out.print("\t");
    System.out.print(root.text + "\n");
    for (TreeNode child : root.children) {
      printTree(child, depth + 1);
    }
  }
}