ACM-ICPC - 2007 - Tag Checker

More Info

Type: Regional
Continent: Oceania
Year: 2001/2002
Link: 2007 - 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:

<B>This is a sentence in boldface</B>

Typically every tag has an opening tag of the form <TAG> and a closing tag of the form </TAG>, 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:

<CENTER><B>This text is centred and in boldface</B></CENTER>

Two of the most common mistakes when tagging text are:

  1. getting the nesting wrong:

<B><CENTER>This should be centred boldface, but the tags are wrongly nested</B></CENTER>

  1. forgetting a tag:

<B><CENTER>This should be centred boldface, but there is a missing tag</CENTER>

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 <T>, <X>, <S>. The corresponding closing tag will be the same letter preceded by the symbol "/". For the examples above these would be </T>, </X>, </S>.

Input

The input will consist of any number of paragraphs. Each paragraph will consist of a sequence of tagged sentences, over as many lines as necessary, and terminating with a # which will not occur elsewhere in the text. The input will never break a tag between two lines and no line will be longer than 80 characters. The input will be terminated by an empty paragraph, i.e. a line containing only a single #.

Output

If the paragraph is correctly tagged then output the line "Correctly tagged paragraph", otherwise output a line of the form "Expected <expected> found <unexpected>" where <expected> 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 text<C><B>is centred and in boldface</B></C>#
<B>This <\g>is <B>boldface</B> in <<*> a</B> <\6> <<d>sentence#
<B><C> This should be centred and in boldface, but the
tags are wrongly nested </B></C>#
<B>This should be in boldface, but there is an extra closing
tag</B></C>#
<B><C>This should be centred and in boldface, but there is
a missing closing tag</C>#
#

Sample Output

Correctly tagged paragraph
Correctly tagged paragraph
Expected </C> found </B>
Expected # found </C>
Expected </B> found #

Solution

Theory

The solution to this problem is really easy. The technique involves using a stack to keep track of the current
open tags.
What you need to do is:

  1. Search for tags.
  2. For each tag found:
    1. If is an opening tag push into the stack
    2. If is a closing tag:
      1. If it is empty then you find a closing tag when everything is closed.
      2. If the top tag is another than the tag you've found a not corresponding tag
      3. If the top tag is the same as the tag you've found then you pop it out and continue.
  3. If you finish processing the tags and everything is fine, you need to check if the stack is empty to detect if there are any tags you haven't closed.

Code

Filename Language Time Memory
2007.cpp C++ 0.484 628
2007.c(Not done yet) C - -
2007.java(Not done yet) Java - -
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License