Cracking Coding Interview - 16.12 XML Encoding

XMLEncoding:Since XML is very verbose, you are given a way of encoding it where each tag gets

mapped to a pre-defined integer value. The language/grammar is as follows:

1
2
3
4
5


Element   --> Tag Attributes END Children END
Attribute --> Tag Value
END       --> 0
Tag       --> some predefined mapping to int
Value     --> string value

For example, the following XML might be converted into the compressed string below (assuming a mapping of family -> 1, person ->2, firstName -> 3, lastName -> 4, state -> 5).

1
2
3


<family lastName="McDowell" state="CA">
  <person firstName="Gayle">Some Message</person>
</family>

Becomes:

1

1 4 McDowell 5 SCA 0 2 3 Gayle 0 Some Message 0 0

Write code to print the encoded version of an XML element (passed in Element and Attribute objects).

Hints: #466

Element和Attribute类：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


public class Element {
  private String tag;
  private List<Attribute> attributes;
  private List<Element> children;
  private String value;
}
public class Attribute {
  private String tag;
  private String value;
}

解法

这个问题看起来可以用递归来解决，步骤大致是：

处理 Element.tag
处理 Element.attributes
添加 END
处理 Element.children，这里重复1-5步
添加 END

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


private static final int END = 0;
public String encodingXml(Element element, Map<String, Integer> tagMap) {
  StringBuilder sb = new StringBuilder();
  encodingXml(element, tagMap, sb);
  return sb.toString()
}
private void encodingXml(Element element, Map<String, Integer> tagMap, StringBuilder sb) {
  sb.append(tagMap.get(element.tag)).append(' ');
  for (Attribute attribute : element.attributes) {
    sb.append(tagMap.get(attribute.tag))
      .append(' ')
      .append(attribute.value);
  }
  sb.append(END).append(' ');
  if (element.value != null) {
    sb.append(element.valule).append(' ');
  }
  for (Element child : element.children) {
    encodingXml(child, tagMap, sb);
  }
  sb.append(END).append(' ');
}

Cracking Coding Interview - 16.12 XML Encoding

解法

版权

评论

Cracking Coding Interview - 16.12 XML Encoding

解法

版权

相关文章

评论