スタックを使ってHTMLの括弧の対応を調べる
5月 7th, 2008 admin Posted in Ruby, 今日のコード | 
昨日学んだスタックの応用でHTMLなどの括弧の対応が正しく取れているかどうかを判定するスクリプトを書きました。
"< "と">"が正しい順番で同じ数になっているかどうかを判定します。
前回リストを使ったスタックを作りましたが今回はRubyの配列Stackを使います。
コード
#>ruby stack.rb < example.html
って感じで使います。
RUBY:
-
$KCODE = "SJIS"
-
str = STDIN.read
-
-
stack = Array.new
-
str.scan(/./) do |c|
-
stack.push(c) if c == "<"
-
if c == ">" && stack.pop.nil?
-
p "括弧の対応が正しくありません。"
-
break
-
end
-
end
-
-
p "括弧の対応が正しくありません。" if stack.size> 0
まとめ
与えられた入力を1文字ずつ処理し、開き括弧（＜）が来たらスタックにプッシュし、閉じ括弧（＞）が来たらポップします。そうすると正しいHTMLの場合は最後にスタックが空になります。
なのでスタックアンダーフローの時と、最後にスタックにデータが残った場合はHTMLにエラーがあるということになるというアルゴリズムです。
括弧の対応を調べるスクリプトを書けと言われるとなんだか複雑なものを考えてしまいますがスタックを使うとこんなに簡単に書けるんだということですね。スタック便利。
※このシリーズは私がRubyでアルゴリズムとデータ構造を基礎から学ぶ記録です。全体の目次はこちらへ。
5月 7th, 2008 at 2:49:03
[...] スタック（括弧の対応を調べる） はてなに追加 MyYahoo!に追加 del.icio.usに追加 livedoorClipに追加 7 Responses to “Rubyでアルゴリズムとデータ構造” [...]