【データ構造】stackについて

データ構造のstackはLIFO（Last In First Out）方式のデータ構造の一種です。

stackについては基本情報技術者試験で学習しましたが、実際に使用する場面はなく知識として頭の中にあっただけでした。最近、LeetCodeでデータ構造とアルゴリズムを学んでおり、そこでstackの問題が出題されたためstackについて復習して行きたいと思います。

問題は以下です。

leetcode.com

文字列として3種類の括弧（"()", "{}", "[]"）が入力として渡され、それが適切な組み合わせかどうかを判定するアルゴリズムを考えます。 条件は以下です。

• 開いている括弧は同じ種類の括弧で閉じなければならない。
• 開いている括弧は正しい順序で閉じなければならない。
• すべての閉じる括弧には対応する同じタイプの開くブラケットが必要。

stackのLIFOの性質を考えると、最後にstackに格納された文字と次の対象の文字を比較することができます。なので、文字が開いている括弧の場合にはstackに格納して、閉じている括弧の場合には最後にstackに格納された文字とを比較して同じ種類か、開いているかを判断すれば良いことになります。それを実装したのが以下のコードです。

class Solution {
public:
    bool isValid(string s) {
      stack<char> stk;
      for (char c : s) {
        if (c == '(' || c == '{' || c == '[') {
          stk.push(c);
        } else {
          if (c == ')' && stk.top() == '(') stk.pop();
          else if (c == '}' && stk.top() == '{') stk.pop();
          else if (c == ']' && stk.top() == '[') stk.pop();
          else return false;
        }
      }
      return stk.empty();
    }
};

しかしこれでは不十分です。 文字列が１文字しかない場合や適切な組み合わせの括弧の間に不適切な括弧がある場合（"(){{}"等）に通りません。これに対応するにはstackがからの場合にfalseを返す処理が必要です。 以下が最終的なコードです。

class Solution {
public:
    bool isValid(string s) {
      stack<char> stk;
      for (char c : s) {
        if (c == '(' || c == '{' || c == '[') {
          stk.push(c);
        } else {
          // ここを追加
          if (stk.empty()) return false;
          if (c == ')' && stk.top() == '(') stk.pop();
          else if (c == '}' && stk.top() == '{') stk.pop();
          else if (c == ']' && stk.top() == '[') stk.pop();
          else return false;
        }
      }
      return stk.empty();
    }
};