C++で有効な括弧文字列を判定する方法（スタックを使ったバランスチェック）

プログラミングにおいて、式の中に含まれる括弧が正しく対応しているか（バランスしているか）を判定することは、構文解析などでよく使われる基本的な処理です。対象となる括弧は ()、{}、[] の3種類です。

例えば、"()[(){()}]" はすべての括弧が正しく入れ子になっているため有効な文字列ですが、"{[}]" は閉じ括弧の順序が対応していないため無効です。

アルゴリズムの考え方

この問題はスタック（stack）を使うことで効率的に解決できます。手順は以下の通りです。

• 式の文字列を先頭から順に走査します。
  • 現在の文字が開き括弧（(、{、[）であれば、スタックにプッシュします。
  • 現在の文字が閉じ括弧（)、}、]）であれば、スタックからポップします。
  • ポップした括弧が、現在の閉じ括弧に対応する開き括弧であれば問題ありません。対応していない場合は、その文字列はバランスしていません。
• 文字列の走査が終わった後、スタックに開き括弧が残っている場合は、閉じられていない括弧が存在するため、その文字列はバランスしていません。

計算量

このアルゴリズムの時間計算量は O(n)、空間計算量もスタックに最大で文字列の長さ分の要素を保持するため O(n) となります。

C++での実装例

以下に、実際の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（後入れ先出し）という性質を活かすことで、直感的かつ効率的に実装できます。この手法は、コンパイラの構文解析やエディタのコード補完機能など、さまざまな場面で応用されている重要なアルゴリズムです。