括弧閉じているかチェック | アルゴリズム [AOJ 1173][Ruby/Python][文字列操作]

引き続きプログラミングの基礎体力づくりと、Pythonの勉強を兼ねてアルゴリズムを勉強中です。今回は『括弧閉じているかのチェック』について勉強しました。AIZU Online Judgeで対応している問題は、『The Balance of the World』です。パズル問題ですが、空き時間が10分あれば十分に解けるお手軽問題ですので、もしお時間があればぜひ!

また、AOJはほかの人の回答を気軽に読むことができます。かなり小さなプログラムですので、可読性と処理の高速性の両立の勉強には持って来いです^^


🎉 AOJ問題

The Balance of the World

Aizu Online Judge。与えられる文字列は、丸括弧(“( )”)と角括弧(“[ ]”)の二種類の括弧を含むことがある。この括弧対応関係が正しいかをチェックする問題。

🐹 Rubyコード

def check_block(str)
q = []
str.gsub(/[^()\[\]]/, '').chars.each do |c|
if c == '(' or c == '['
q.push(c)
elsif c == ')'
r = q.pop() rescue nil
return 'no' if r != '('
elsif c == ']'
r = q.pop() rescue nil
return 'no' if r != '['
end
end
q.count == 0 ? 'yes' : 'no'
end
while gets
break if $_.chomp == '.'
puts check_block($_.chomp)
end

🚜 Pythonコード

while True:
s = raw_input()
if s == '.': break
ns = ''
for c in s:
if c in ['(', ')', '[', ']']:
ns += c
while True:
tmp = ns
ns = ns.replace('[]', '')
ns = ns.replace('()', '')
if (tmp == ns): break
print 'no' if ns else 'yes'

🚌 GitHubリポジトリ

当面はAOJを解きながら、アルゴリズムの再勉強をしていくつもりです。Ruby/PythonでのAOJの回答は下のリポジトリに保存しておきます。もしツッコミとかあればぜひ^^

morizyun/aoj-ruby-python - GitHub

📚 おすすめの書籍

💩 欲しいものリスト公開しました