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