LeetCode 20. 有効な括弧 (Valid Parentheses)

スタック（Stack）はLIFO（後入れ先出し）の特性を持つため、括弧の対称性チェックのようなネスト構造の検証に適しています。実装の際は、不一致が発生するすべてのエッジケースを事前に分析することが重要です。

アルゴリズムのアプローチとして、左括弧が現れた際に、対応する「期待される右括弧」をスタックにプッシュする手法があります。これにより、探索中の文字が右括弧である場合、スタックの最上部要素（期待値）と比較するだけで整合性を確認できます。

考慮すべき主な不一致パターンは以下の通りです：

1. 文字列の走査が完了した後もスタックが空ではない（左括号が余っている）。
2. 走査中に右括弧が出現したが、スタックが空である（対応する左括号がない）。
3. 右括弧がスタックの最上位要素と一致しない（括弧の種類が違う）。

最終的に文字列を走査し終えたときにスタックが空であれば、すべての括弧が正しくペアリングされていることを示します。

class Solution {
public:
    bool isValid(string s) {
        // 文字数が奇数の場合、ペアになり得ないため早期リターン
        if (s.size() % 2 != 0) return false;
        
        stack<char> charStack;
        for (char current : s) {
            // 左括弧の場合は対応する右括号をプッシュ
            if (current == '(') {
                charStack.push(')');
            } else if (current == '{') {
                charStack.push('}');
            } else if (current == '[') {
                charStack.push(']');
            } else {
                // 右括弧、またはその他の文字の場合
                // スタックが空、あるいは期待する括弧と一致しない場合は無効
                if (charStack.empty() || charStack.top() != current) {
                    return false;
                }
                // 一致した場合はスタックから取り出す
                charStack.pop();
            }
        }
        // すべてのペアがマッチしていればスタックは空になっているはず
        return charStack.empty();
    }
};

LeetCode 1047. 隣接する重複文字の削除 (Remove All Adjacent Duplicates In String)

この問題もスタックの特性を活用した典型例です。スタックを使用することで、現在処理している文字の「直前の文字」を常に参照することができ、隣接する文字の比較を効率的に行えます。

基本的なロジックは、スタックの最上部にある要素と現在見ている要素を比較し、一致していれば削除（ポップ）、一致しなければ追加（プッシュ）するというものです。最終的にスタックに残った要素が答えとなります。C++ではstd::string自体がpush_backやpop_backを持っているため、明示的なスタックを使わずに文字列をスタックとして扱うことで、結果の反転処理を省略し、パフォーマンスとコードの簡潔性を向上させることができます。

class Solution {
public:
    string removeDuplicates(string s) {
        string result;
        for (char c : s) {
            // 結果文字列（スタック代わり）の末尾と現在の文字を比較
            if (!result.empty() && result.back() == c) {
                result.pop_back(); // 重複しているため削除
            } else {
                result.push_back(c); // 重複していないため追加
            }
        }
        return result;
    }
};

LeetCode 150. 逆ポーランド記法の評価 (Evaluate Reverse Polish Notation)

逆ポーランド記法（RPN）は、演算子をオペランドの後に配置する記法です。この数式の評価にはスタックが不可欠です。

処理の流れは以下の通りです：

1. トークン（数字または演算子）を左から右に順に読み込む。
2. 数字の場合はスタックにプッシュする。
3. 演算子の場合は、スタックから2つの数字をポップし、その演算を行って結果をスタックにプッシュする。

注意点として、一部のテストケースではオーバーフローを防ぐためにlong long型を使用する必要があります。文字列から数値への変換にはstoll関数を用います。

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<long long> calcStack;
        
        for (const string& token : tokens) {
            // 演算子の判定
            if (token == "+" || token == "-" || token == "*" || token == "/") {
                // 後に入った要素が第1オペランド、先に入った要素が第2オペランド
                long long val1 = calcStack.top(); calcStack.pop();
                long long val2 = calcStack.top(); calcStack.pop();
                
                if (token == "+") calcStack.push(val2 + val1);
                else if (token == "-") calcStack.push(val2 - val1);
                else if (token == "*") calcStack.push(val2 * val1);
                else if (token == "/") calcStack.push(val2 / val1);
            } else {
                // 数値の場合は文字列から数値に変換してプッシュ
                calcStack.push(stoll(token));
            }
        }
        
        return calcStack.top();
    }
};