作者:渡部有隆
マイナビ出版

背景

プログラミングテストの練習問題として、
ハッシュマップとスタックを利用した
Valid Parentheses問題を解いたので、
その解法をメモしておく。

問題

下記のような3種類のカッコで構成された文字列が与えられるとする。

'(', ')', '[', ']', '{', '}'

その与えられた文字列に対して、下記の条件を満たせばValid、
そうでなければInvalidと判定するアルゴリズムを実装する。

左カッコが、同じ種類の右カッコによって閉じられる
各種左カッコが正しい順番で右カッコにより閉じられている

例えば、

文字列が"()"ならValid, "(]"ならInvalidと判定される。

解法

まずは、同種類のカッコのペアリングを定義するために、
ハッシュマップを利用する。

vivi.dyndns.org

ここでは、各種類の右カッコをキー、左カッコを値に割り当てる。

そして、与えられた文字列がValidか判定するためにスタックを
利用する。
bituse.info

これら2種類のデータ構造を利用したアルゴリズムは下記のようになる。

スタックを初期化
文字列に含まれるカッコを左から順番に参照
2で参照したのが左カッコだったら、スタックに格納
2で参照したのが右カッコだったら、スタックの一番上にある要素を参照
スタックの一番上の左カッコが同種類なら、popしてスタックから削除
5の時点でpopできないようなら、その文字列はInvalidと判定して終了
2~6を最後のカッコまで繰り返す
最後に、まだスタックに要素が残っているようなら、その文字列はInvalidと判定

f:id:sy4310:20220319221820p:plain

このアルゴリズムを実装したC++サンプルコードは下記のようになる。

#include <iostream>
#include <unordered_map>
#include <stack>

using namespace std;

class ValidParentheses {
  private:
    // hash table that takes care of the mappings
    unordered_map<char, char> mappings;
  public:
    // initialize hash map with mappings
    ValidParentheses() {
      this->mappings[')'] = '(';
      this->mappings['}'] = '{';
      this->mappings[']'] = '[';
    }

    void is_valid(string input) {
      // initialize a stack to be used in the algorithm
      stack<char> stack_char;

      for (int i = 0; i < input.length(); i++) {
        char c = input[i];

        // if the current character is a closing bracket
        if (this->mappings.find(c) != this->mappings.end()) {
          // get the top of element of the stack
          // if the stack is empty, set a dummy value of '#'
          char top_element;
          if (stack_char.empty()) {
            top_element = '#';
          }
          else {
            top_element = stack_char.top();
            stack_char.pop();
          }

          if (top_element != this->mappings[c]) {
            cout << input << " is invalid" << endl;
            return;
          }
        }
        else {
          // if it was an opening bracket, push to the stack
          stack_char.push(c);
        }
      }

      if (stack_char.empty()) cout << input << " is valid" << endl;
      else cout << input << " is invalid" << endl;
    }
};

int main(void) {
  ValidParentheses vp;

  // test case 1
  string input_1 = "()";
  vp.is_valid(input_1);

  // test case 2
  string input_2 = "()[]{}";
  vp.is_valid(input_2);

  // test case 3
  string input_3 = "(]";
  vp.is_valid(input_3);
  
  return 0;
}