#5 Stacks: Balanced Brackets
括弧記号のみで構成される文字列が入力として渡される。
{, }, (, ), [, ]
文字列の括弧が均衡していれば、YES、それ以外は NO を出力する。
例えば{[(])}は均衡していない。なぜなら閉じていない([) 部分の(が閉じられていないから。
{[(])} # NO
{[()]} # YES
solution
table = {"[" => "]", "(" => ")", "{" => "}"}
input = $stdin.read.split("\n")
n, l = input.shift.to_i, input
l.each do |str|
stack = []
str.split("").each do |c|
if !stack.empty? && "])}".include?(c)
break if table[stack.last] != c
stack.pop
else
stack.push(c)
end
end
puts stack.empty? ? "YES" : "NO"
end
スタックとは
この類いの問題は上記のように配列でスタックを実現することによって簡単に解くことができる。
スタックは、コンピュータで用いられる基本的なデータ構造の1つで、データを後入れ先出し（LIFO: Last In First Out; FILO: First In Last Out）の構造で保持するものである。抽象データ型としてのそれを指すこともあれば、その具象を指すこともある。
