酒と泪とRubyとRailsと

Ruby on Rails と Objective-C は酒の肴です!

アルゴリズムの勉強: カッコが閉じているかチェック[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のサンプルソース

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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のサンプルソース

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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'

Aizu Online Judgeのサンプルソース

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

morizyun/aoj-ruby-python - GitHub

最近解いたAOJの問題

AOJタグのついた最近解いた問題一覧

おすすめの書籍