トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

GeeksforGeeks(括弧の整合性チェック)

[GeeksforGeeks,アルゴリズム]

GeeksforGeeks(括弧の整合性チェック)

括弧の整合性チェック

文字列の表現が与えられた時、括弧(“{“,”}”,”(“,”)”,”[“,”]”)のペアと順序が正しいかどうかテストするためのプログラムを書きましょう。例えば、プログラムは“[()]{}{[()()]()}”にはtrueを返し、“[(])”にはfalseを返すべきです。

  アルゴリズム

  1. 文字列のスタックSを宣言する
  2. 文字列表現を探索する
    1. もし現在の文字が開始タグであればスタックにプッシュ
    2. もし現在の文字が閉じタグであればスタックからポップを実行し、ポップされた文字が開始タグと一致した場合整合性がとれている、そうでない場合は不整合
  3. 全ての探索が終わった後、もしスタックに開始タグが残っていればそれも不整合である

  サンプルコード

def stag?(s)
  s=='(' or s=='[' or s=='{'
end

def etag?(s)
  s==')' or s==']' or s=='}'
end

def paren_balanced?(expr)
  s = []
  # Traversing the Expression
  for i in 0...expr.length
    if stag?(expr[i])
      # Push the element in the stack
      s.push(expr[i])
      next
    end
    # IF current character is not opening
    # bracket, then it must be closing.
    # So stack cannot be empty at this point.
    if s.empty?
      false
    else
      case expr[i]
      when ')' then
        x = s.last
        s.pop
        return false if x=='{' or x=='['
      when '}' then
        x = s.last
        s.pop
        return false if x=='(' or x=='['
      when ']' then
        x = s.last
        s.pop
        return false if x=='(' or x=='{'
      end

      next
    end
  end
  s.empty?
end

expr = "{()}[]"

if paren_balanced?(expr)
  puts "Balanced"
else
  puts "Not Balanced"
end
お名前: コメント: