JSON Parser

Introduction

In this assignment you will work on a toy JSON parser. JSON is a popular text format used for serialization of primitive data types, arrays and objects (represented by key-value pairs). You can read more about JSON on Wikipedia ( http://en.wikipedia.org/wiki/JSON ) and its official website ( http://json.org/ ).

Your task is to implement a parser for JSON stored in text files with specific formatting (to avoid the need for complex parsing techniques) where every value or control character is stored on a separate line:

{
"example"
:
[
"string 1"
,
"string 2"
]}

For simplicity's sake, only strings will be used as values in JSON files used for this assignment.

Exercise 1

Implement a Queue ADT for generic element types that supports the following operations:

• enqueue an element in O(1)
• dequeue an element in O(1)
• peek the front element in O(1)
• return queue length in O(1)

Your class must implement the interface provided in file "A1Queue.java".

A reminder: you may implement your ADTs from scratch or use existing classes from Java standard library in some way.

Exercise 2

Implement a Stack ADT for generic element types that supports the following operations:

• push an element in O(1)
• pop an element in O(1)
• peek the top element in O(1)
• return stack size in O(1)

Your class must implement the interface provided in file "A1Stack.java".

Exercise 3

Implement a TreeNode ADT for generic element types that supports the following operations:

• check if node is a JSON object
• check if node is a JSON array
• check if node is a JSON primitive value

Your class must implement the interface provided in file "A1TreeNode.java".

Exercise 4

Implement a Tree ADT for generic element types that supports the following operations:

• return the reference to the root A1TreeNode
• insert a A1TreeNode element as a child of specified A1TreeNode
• return tree size (number of elements) in O(1)
• print tree in a formatted way (see further)

Your class must implement the interface provided in file "A1Tree.java".

Hint: it is assumed that "null" will be specified as the parent node when inserting the first (root) node into the tree.

Exercise 5

Using the data types implemented in previous exercises, implement a class that would:

• read the contents of a specified JSON file line by line
• enqueue each line to a A1Queue[String]
• afterwards, analyze the contents of the queue and construct the A1Tree for JSON document
• print the resulting tree

Your class must implement the interface provided in file "A1Main.java".

Hint: to process nested data structures in JSON document, you should maintain a A1Stack of nodes that are parents to each other and pop elements from the stack when encountering a control character like "]" or "}".

While printing the tree, correct indentation must be preserved (you can choose the policy for printing control characters for yourself).