私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「htmlタグの入れ子の違い」（CodeIQ）を参照してください。
【問題】
htmlが標準入力から与えられるので、htmlタグの入れ子が間違っている、閉じタグが現れる最初の行番号を、標準出力に出力するプログラムを作ってください。
htmlは最大20行、1行あたり最大100文字です。
ただし、liタグに関しては、タグが閉じていても閉じてなくてもよいものとします。
間違いがない場合には0を出力してください。
Rubyで解答しています。
#!/usr/bin/ruby
# タグの対応をチェックする
# @param stack これまでに見つかったタグのリスト
# @param tag 今回処理するタグ
# @return true:対応は正しい、false:対応に間違いがある
def check(stack, tag)
# printf("input = %s\n", tag)
singles = ["br", "img"] # 単独で使用されるタグ
single_or_end = ["li"] # 単独でも終了タグと一組でも使用されるタグ
if singles.include?(tag) then return true
else
# 終了タグの場合
if tag[0] == '/' then
st = stack.pop
# printf("start tag=%s\n", st)
if st == tag[1, tag.size-1] then return true
elsif single_or_end.include?(st) then return check(stack, tag)
else return false
end
else
stack << tag
end
end
end
# main
stack = []
lno = 0
while line = gets
lno += 1
line.strip!
if line.empty? then next end
if tags = line.scan(/<.+?>/) then
for t in tags
t = t[1, t.size-2] # <と>を除く
t = t.split[0] # 属性を無視する
if check(stack, t.downcase) == false then
p lno
exit
end
end
end
end
p 0
前にも同じような問題をやったことがある気がします。
ただ、こちらの方がちょっと難しいです。タグの属性については問題文に言及がありませんが考慮する必要があります。実際、テストケースには属性が含まれていました。
タグの入れ子違いのチェックのような問題はスタックを使って処理するのが常套手段と思います。
開始タグが見つかったらスタックに積み、終了タグが見つかったらスタックから取り出して対応をチェックします。ただ、単独で機能するタグはスタックに積む時に無視します。
あと今回は<li>が終了タグのあり・なし両方に対応しなければならないのでそれを考慮します。
読み込んだ1行ずつ処理します（33〜50行目）。
読み込んだ行から<タグ名>か</タグ名>を複数タグがある可能性があることを考慮して全て抜き出します（39行目）。
行にタグが1つ以上あったら見つかったタグの数だけループして処理します（40〜48行目）。
この時タグの<>と属性を除きます（41、42行目）。属性は最初のスペース以降なのでタグから<>とったものを空白文字で分割した最初の文字列がタグ名になります。
check()はタグが開始タグならスタックに積み、終了タグなら対応をチェックしておかしければfalseを返す関数です。この関数にタグを渡してfalseが帰ってきたらその行番号を表示して終了します（44〜47行目）。
ループが最後まで回ったら対応に問題はないので0を印字します（52行目）。
引数stackはこれまでに見つかった開始タグを積んでおくスタック、tagは新しく渡されるタグから<>と属性を除いた文字列です。終了タグの「/」はつけたままです。
定数singlesは単独で機能するタグです。種類が足りていませんがテストケースでエラーになったら増やせば良いと思ってやったら、これでテストケースを通ってしまいました。増やす必要はありますがロジックには関係ありません。
single_or_endは終了タグを省略して良いタグです。今回の問題では<li>だけです。
まず、singlesに含まれるタグなら無視します（13行目）。
終了タグの場合（16〜22行目）、スタックから最後に追加されたタグを取り出し（17行目）、引数tagの先頭の「/」を除いたものと取り出したタグ名を比較します（19行目）。同じならtrueを返します。一致せず、取り出したタグがsingle_or_endに含まれる場合、check()を再帰的に呼び出します。
例えば、スタックに["div", "li", "li"]と積まれていた時に"/div"がきたとします。最初の呼び出しで"li"が取り出され20行目の条件にヒットします。スタックが["div", "li"]で再度check()を呼び出し、同じように"li"が取り出され20行目の条件にヒットして今度はスタックが["div"]でcheck()が呼び出されます。この時点でタグの一致が確認できてtrueが帰るという仕組みになっています。
21行目は取り出したタグと引数tagの対応が確認できなかった場合の条件です。
引数tagに渡ってきたのが終了タグでなかったらスタックに積んで終わります（24行目）。
ここで明示的にtrueを返していないのはよくありません。
本文中にも書いた通り単独タグのリストが不足しています。本来なら不合格になるべきテストケースがあるはずなのですが、合格してしまいました。まぁ、単独タグのリストに追加すれば本当に正しく動作するので良いや、ということで再提出はしていません。
あと、<!DOCTYPE 〜>も無視するようにしておく必要がありました。
ちなみに、この問題のテストケースはタグを閉じ忘れて終わっている場合は間違いなしとして扱ってしまいます。どうせなら閉じ忘れもチェックするような問題にしておけば良かったのに、と思いました。