C++でスタックを使って括弧の対応（バランス）をチェックするプログラム

この記事では、スタック（Stack）というデータ構造を活用して、式の中の括弧が正しく対応しているかどうか（バランスが取れているか）を判定する方法を解説します。単に開き括弧と閉じ括弧の数が一致しているかを確認するだけでなく、括弧の順序（入れ子の関係）が正しいかどうかもチェックできる点がポイントです。

例えば、式「[{}(){()}]」は括弧の対応が正しいため妥当な式ですが、「{[}]」は閉じ括弧の順序が誤っているため不正な式となります。

入力：括弧を含む式 "{()}[]"
出力：They are balanced（バランスが取れている）

アルゴリズム

スタックのLIFO（後入れ先出し）という性質を利用することで、最後に開いた括弧が最初に閉じられるべきという括弧のルールを自然に検証できます。手順は以下の通りです。

1. 括弧を格納するためのスタックを定義する。
2. 式を左から右へ1文字ずつ走査する。
   • 文字が開き括弧「(」「{」「[」の場合、スタックにプッシュする。
   • 文字が閉じ括弧「)」「}」「]」の場合、スタックからポップし、取り出した文字が対応する開き括弧と一致していれば問題なし。一致しなければバランスが取れていないと判定する。
3. 走査終了後、スタックに開き括弧が残っている場合はバランスが取れていないと判断する。

C++による実装例

#include<iostream>
#include<stack>
using namespace std;

bool isBalanced(string expr) {
    stack<char> s;
    char ch;
    // 式内の各文字について条件を判定
    for (int i = 0; i < expr.length(); i++) {
        // 開き括弧ならスタックにプッシュ
        if (expr[i]=='('||expr[i]=='['||expr[i]=='{') {
            s.push(expr[i]);
            continue;
        }
        // 開き括弧以外なら、スタックが空の時点で不正（閉じ括弧が先に来ている）
        if (s.empty())
            return false;
        switch (expr[i]) {
            case ')': // 閉じ丸括弧：ポップして波括弧・角括弧でないか確認
                ch = s.top();
                s.pop();
                if (ch=='{' || ch=='[')
                    return false;
                break;
            case '}': // 閉じ波括弧：ポップして丸括弧・角括弧でないか確認
                ch = s.top();
                s.pop();
                if (ch=='(' || ch=='[')
                    return false;
                break;
            case ']': // 閉じ角括弧：ポップして丸括弧・波括弧でないか確認
                ch = s.top();
                s.pop();
                if (ch=='(' || ch=='{')
                    return false;
                break;
        }
    }
    // スタックが空ならバランス取れている（true）
    return (s.empty());
}

main() {
    string expr = "[{}(){()}]";
    if (isBalanced(expr))
        cout << "Balanced";
    else
        cout << "Not Balanced";
}

実行結果

Balanced

処理のポイントと計算量

このアルゴリズムでは、式を一度だけ走査すればよいため、時間計算量はO(n)、スタックに格納される要素は最大で式の長さ分となるため空間計算量もO(n)です。

特に注意すべきケースは以下の通りです。

• 閉じ括弧が先に現れる場合：「)(」のように、スタックが空の状態で閉じ括弧が来たら即座に不正と判定します。
• 種類の異なる括弧が交差する場合：「{[}]」のように、ポップした開き括弧が閉じ括弧と対応していない場合は不正と判定します。
• 開き括弧が余る場合：「(()」のように、走査終了後にスタックが空でなければ不正と判定します。

このように、スタックを使った括弧対応チェックは、コンパイラや構文解析器、エディタのシンタックスハイライトなど、さまざまな場面で応用される基本的かつ重要なアルゴリズムです。