GeeksforGeeks(括弧の整合性チェック)
括弧の整合性チェック
文字列の表現が与えられた時、括弧（“{“,”}”,”(“,”)”,”[“,”]”）のペアと順序が正しいかどうかテストするためのプログラムを書きましょう。例えば、プログラムは“[()]{}{[()()]()}”にはtrueを返し、“[(])”にはfalseを返すべきです。
アルゴリズム
- 文字列のスタックSを宣言する
- 文字列表現を探索する
- もし現在の文字が開始タグであればスタックにプッシュ
- もし現在の文字が閉じタグであればスタックからポップを実行し、ポップされた文字が開始タグと一致した場合整合性がとれている、そうでない場合は不整合
- 全ての探索が終わった後、もしスタックに開始タグが残っていればそれも不整合である
サンプルコード
def stag?(s)
s=='(' or s=='[' or s=='{'
end
def etag?(s)
s==')' or s==']' or s=='}'
end
def paren_balanced?(expr)
s = []
# Traversing the Expression
for i in 0...expr.length
if stag?(expr[i])
# Push the element in the stack
s.push(expr[i])
next
end
# IF current character is not opening
# bracket, then it must be closing.
# So stack cannot be empty at this point.
if s.empty?
false
else
case expr[i]
when ')' then
x = s.last
s.pop
return false if x=='{' or x=='['
when '}' then
x = s.last
s.pop
return false if x=='(' or x=='['
when ']' then
x = s.last
s.pop
return false if x=='(' or x=='{'
end
next
end
end
s.empty?
end
expr = "{()}[]"
if paren_balanced?(expr)
puts "Balanced"
else
puts "Not Balanced"
end