Test task in passing the interview
Tag Checker Problem
Markup languages such as HTML use tags to highlight sections with special significance. In this way, a sentence
in boldface can be indicated thus:
This is a sentence in boldface
Typically every tag has an opening tag of the form and a closing tag of the form , so that portions
of text can be bracketed as above. Tags can then be combined to achieve more than one effect on a particular piece
of text simply by nesting them properly, for instance:
This text is centred and in boldface
Two of the most common mistakes when tagging text are:
getting the nesting wrong:
This should be centred boldface, but the tags are wrongly nested
forgetting a tag:
This should be centred boldface, but there is a missing tag
Write a program to check that all the tags in a given piece of text (a paragraph) are correctly nested, and that there
are no missing or extra tags. An opening tag for this problem is enclosed by angle brackets, and contains exactly
one upper case letter, for example , , . The corresponding closing tag will be the same letter preceded
by the symbol /; for the examples above these would be , , .
If the paragraph is correctly tagged then output the line “Correctly tagged paragraph”, otherwise output a line of
the form “Expected found ” where is the closing tag matching the most
recent unmatched tag and is the closing tag encountered. If either of these is the end of paragraph,
i.e. there is either an unmatched opening tag or no matching closing tag at the end of the paragraph, then replace
the tag or closing tag with #. These points are illustrated in the examples below which should be followed exactly
as far as spacing is concerned.
Sample Input
The following textis centred and in boldface
This <\g>is boldface in <<*> a <\6> <sentence
This should be centred and in boldface, but the
tags are wrongly nested
This should be in boldface, but there is an extra closing
tag
This should be centred and in boldface, but there is
a missing closing tag
Sample Output
Correctly tagged paragraph
Correctly tagged paragraph
Expected found
Expected # found
Expected found #