C++で括弧のバランスを判定する方法：スタックを使った有効な括弧チェック

問題の概要

ある式が与えられたとき、その式に含まれる括弧が正しく対応している（バランスしている）かどうかを判定します。対象となる括弧は ()、{}、[] の3種類です。

例えば、「()[(){()}]」は開き括弧と閉じ括弧が正しい順序で対応しているため有効な式です。一方、「{[}]」は括弧の入れ子関係が崩れているため無効となります。

アルゴリズムの考え方：スタックを活用する

この問題はスタック（stack）というデータ構造を使うことで、シンプルかつ効率的に解決できます。手順は以下の通りです。

• 式を先頭から最後まで走査する
  • 現在の文字が開き括弧（(、{、[）の場合 → スタックにプッシュする
  • 現在の文字が閉じ括弧（)、}、]）の場合 → スタックからポップし、取り出した開き括弧が現在の閉じ括弧と対応しているかを確認する。対応していれば問題なし、そうでなければその式はバランスしていない
• 走査終了後の確認 → 文字列をすべて処理した後もスタックに開き括弧が残っている場合は、閉じられていない括弧が存在するため、その式はバランスしていないと判定する

この手法により、計算量は式の長さを n としたとき O(n) で済みます。

C++での実装例

#include <iostream>
#include <stack>
using namespace std;
bool isBalancedExp(string exp) {
    stack<char> stk;
    char x;
    for (int i=0; i<exp.length(); i++) {
        if (exp[i]=='('||exp[i]=='['||exp[i]=='{') {
            stk.push(exp[i]);
            continue;
        }
        if (stk.empty())
            return false;
        switch (exp[i]) {
        case ')':
            x = stk.top();
            stk.pop();
            if (x=='{' || x=='[')
                return false;
            break;
        case '}':
            x = stk.top();
            stk.pop();
            if (x=='(' || x=='[')
                return false;
            break;
        case ']':
            x = stk.top();
            stk.pop();
            if (x =='(' || x == '{')
                return false;
            break;
        }
    }
    return (stk.empty());
}
int main() {
    string expresion = "()[(){()}]";
    if (isBalancedExp(expresion))
        cout << "This is Balanced Expression";
    else
        cout << "This is Not Balanced Expression";
}

実行結果

入力

"()[(){()}]"

出力

This is Balanced Expression

まとめ

括弧の対応チェックは、スタックの「後入れ先出し（LIFO）」の性質を利用することで自然に実装できます。開き括弧をプッシュし、閉じ括弧が出たら直近の開き括弧と照合する——この流れさえ押さえれば、ネストされた複雑な式でも確実に判定可能です。コンパイラや構文解析ツールなどでも使われる基本的なテクニックなので、ぜひマスターしておきましょう。