括弧閉じているかチェック | アルゴリズム [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

🖥 VULTRおすすめ

VULTR」はVPSサーバのサービスです。日本にリージョンがあり、最安は512MBで2.5ドル/月($0.004/時間)で借りることができます。4GBメモリでも月20ドルです。 最近はVULTRのヘビーユーザーになので、「ここ」から会員登録してもらえるとサービス開発が捗ります!

📚 おすすめの書籍