Problems:

The eXtended Markup Language (XML) is a widely used format for describing structured data.

An XML document is a collection of matching start-tags and end-tags. A start-tag is a string of alphabetic characters preceded by a . For example is a start-tag of type "foo".

An end-tag is an alphabetic string preceded by and terminated by a >. For example is an end-tag of type "foo".

Well-formed XML requires that start-tags and end-tags match (i.e. have the same type.)

Examples

XML Valid? Explanation

Yes "a" tags balance

Yes "a" outer tags and "b" inner tags balance

No "a" end-tags does not match start-tag ("b")

Yes all tags balance

No "Baker" end-tag does not match start-tag ("baker") (i.e. the tag names are case-sensitive.)

The Algorithm

The algorithm to determine if the start and end-tags balance uses a Stack data structure to keep track of previously read start-tags. The algorithm is:

1. Read the input until the beginning of a tag is detected. (i.e. tags begin with <. if the next character is a then it an end-tag otherwise start-tag>

2. Read the tag's identity. (e.g. both tags and have the same identity 'x').

3. If the tag was a start-tag, push it onto the Stack.

4. Otherwise, it is an end-tag. In this case, pop the Stack (which contains a previously pushed start-tag identity) and verify that the popped identity is the same as the end-tag just processed. Note: if the stack cannot be popped (because it is empty), the input is invalid; the algorithm should STOP.

5. If the identities do not match, the XML expression is invalid. STOP.

6. If they do match, then no error has been detected (yet!).

7. If there is still input that has not yet been processed, go back to the first step.

8. Otherwise (no more input) then the input is valid unless the Stack is not empty. Indicate whether the input is valid (Stack empty) or invalid and STOP.

Part 1: Validation of single-character tags

We begin with a simplified XML that restricts tag identifiers to single-character lower case letters. (i.e. there are only 26 valid tags).

Objective:

Your program (called validateXML) reads stdin and determines if it is valid XML. If it is valid, it prints to stdout the message "Valid" and exits with an exit code of 0 (zero); otherwise, it prints "NOT Valid" and exits with an exit code of 1 (one).

Note

Nothing else should be printed to stdout. (For example, if the input is invalid, the program does not have to explain the problem it found.) However, additional information may be printed to stderr. Indeed, in the case of Stack underflow or overflow, a message should be printed to stderr.

You need to create a main() function that reads stdin and processes each character according to the algorithm. You also need to implement a Stack

Part 2: Validating and counting of single-character tags

Objective:

In addition to validating the input, your program should also keep track of the number of times each start-tag is used. As before, the program should print "Valid" or "NOT Valid". In addition, if the input was valid, it should then print a table with a line for each start-tag encountered and a count of how often it occurred.

For example, given the input:

The output should be:

Valid

a 2

b 1

x 1

y 1

Don't use this code

private boolean isTagBalanced(String s) Stack stack = new Stack(); fortint i = 0; i