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