スコーンの開発日記

開発中の学びをまとめていく。

Rubyでスタックを扱う

Ruby algorithm

LeetCodeで面白い問題を見つけたので、理解を深めるために復習する。 スタックを使ったアルゴリズム。

leetcode.com

問題

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  • Open brackets must be closed by the same type of brackets.
  • Open brackets must be closed in the correct order.
  • Note that an empty string is also considered valid.

つまり、カッコが適切に閉じられていればtrue、そうでなければfalseを返すようにせよ、という問題。

Example 1:

Input: "()"
Output: true

Example 2:

Input: "()[]{}"
Output: true

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true



考えてみよう

LeetCodeのSolutionをたどっていく。


カッコが1種類だったら

まずカッコが1種類()しかないケースを考える。

(((((()))))) -- VALID

()()()()     -- VALID

(((((((()    -- INVALID

((()(())))   -- VALID

この場合は、以下のアルゴリズムで解決できる。

  1. We process the expression one bracket at a time starting from the left.

  2. Suppose we encounter an opening bracket i.e. (, it may or may not be an invalid expression because there can be a matching ending bracket somewhere in the remaining part of the expression. Here, we simply increment the counter keeping track of left parenthesis till now. left += 1

  3. If we encounter a closing bracket, this has two meanings:

    1. One, there was no matching opening bracket for this closing bracket and in that case we have an invalid expression. This is the case when left == 0 i.e. when there are no unmatched left brackets available.
    2. We had some unmatched opening bracket available to match this closing bracket. This is the case when left > 0 i.e. we have unmatched left brackets available.

  4. If we encounter a closing bracket i.e. ) when left == 0, then we have an invalid expression on our hands. Else, we decrement left thus reducing the number of unmatched left parenthesis available.

  5. Continue processing the string until all parenthesis have been processed.

  6. If in the end we still have unmatched left parenthesis available, this implies an invalid expression.


つまり、


  1. 左から1つずつ処理する
  2. opening bracketだけではinvalid判定はできないので、left += 1
  3. closing bracketは、以下のいずれか
    1. マッチするopening bracketがいなかった(left == 0のとき)
    2. 未マッチのopening bracketがいる (left > 0のとき)
  4. left == 0でclosing bracketが出たらinvalid。left -= 1
  5. 以上の処理を最後まで繰り返す
  6. left != 0ならばinvalid

しかし3種類のカッコには対応できない

しかしこの方法では3種類のカッコに対応することはできない。3種類それぞれにleftの変数を用意すればよいのでは？と考えるかもしれないが、それだと以下のケースでもvalidとなってしまう。

[{]
# => 本当はinvalidなのにvalid扱いになる



解法

アルゴリズム

スタックとして処理すればよい。

  1. Initialize a stack S.
  2. Process each bracket of the expression one at a time.
  3. If we encounter an opening bracket, we simply push it onto the stack. This means we will process it later, let us simply move onto the sub-expression ahead.
  4. If we encounter a closing bracket, then we check the element on top of the stack. If the element at the top of the stack is an opening bracket of the same type, then we pop it off the stack and continue processing. Else, this implies an invalid expression.
  5. In the end, if we are left with a stack still having elements, then this implies an invalid expression.


つまり、


  1. スタック型のデータSを初期化する
  2. カッコを1つずつ処理する
  3. opening bracketならばスタックSに入れて、次に進む
  4. closing bracketならばスタックSに入っている一番上のカッコを見て、同じ種類ならばpopして次に進む。同じ種類でなければinvalid
  5. 最後まで処理してもスタックに残っていたらinvalid



Rubyで書いてみる

# @param {String} s
# @return {Boolean}
def is_valid(s)
    stack = []
    
    s.split('').each do |char|
        if MAPPING.key?(char)
            top_element = stack.size > 0 ? stack.pop : '#'
            return false if MAPPING[char] != top_element
        else
            stack.push(char)
        end
    end
    stack.empty?
end

MAPPING = {
          ")" => "(",
          "}" => "{",
          "]" => "["
          }

コメントをつけるとこうなる。

# @param {String} s
# @return {Boolean}
def is_valid(s)
    # opening bracketsを入れていくスタック
    stack = []
    
    s.split('').each do |char|
        if MAPPING.key?(char)
            # closing bracketの場合
            # スタックの中身がある場合は一番上の要素と比較。無い場合はinvalid
            top_element = stack.size > 0 ? stack.pop : '#'
            return false if MAPPING[char] != top_element
        else
            # opening bracketの場合
            # スタックに入れる
            stack.push(char)
        end
    end
    stack.empty?
end

MAPPING = {
          ")" => "(",
          "}" => "{",
          "]" => "["
          }

なるほど、popの返り値が配列から落とした値である理由がわかった。pushとpopは配列をスタックとして扱ってるんやな。



参考

leetcode.com

en.wikibooks.org