Write a program in C++ to validate a user entered XML expression.

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 / (slash), then it is an end-tag; otherwise it is a 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.

Examples of User Input

	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.)

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