C++でのバランスした括弧の解決方法

バランスした括弧の問題は、与えられた文字列に含まれる括弧が正しく対応しているかどうかを判断することです。例えば、文字列 "([])" はバランスしていますが、"(]" や "([)]" はバランスしていません。

以下に、いくつかの方法を示します。

スタックを使用する方法: この方法では、スタックというデータ構造を使用して括弧の対応関係を管理します。文字列を一文字ずつ読み込み、開き括弧（'(', '[', '{'）をスタックにプッシュし、閉じ括弧（')', ']', '}'）が現れた場合は、スタックのトップの括弧と対応するかどうかをチェックします。対応していれば、スタックからその括弧をポップします。最終的に、スタックが空であれば括弧はバランスしています。以下にC++のコード例を示します:

#include <iostream>
#include <stack>
using namespace std;
bool isBalanced(string s) {
   stack<char> st;
   for (char c : s) {
       if (c == '(' || c == '[' || c == '{') {
           st.push(c);
       } else if (c == ')' || c == ']' || c == '}') {
           if (st.empty()) {
               return false;
           } else if ((c == ')' && st.top() == '(') ||
                      (c == ']' && st.top() == '[') ||
                      (c == '}' && st.top() == '{')) {
               st.pop();
           } else {
               return false;
           }
       }
   }
   return st.empty();
}
int main() {
   string s;
   cout << "Enter a string: ";
   cin >> s;
   if (isBalanced(s)) {
       cout << "Balanced" << endl;
   } else {
       cout << "Not balanced" << endl;
   }
   return 0;
}

カウンターを使用する方法: この方法では、開き括弧と閉じ括弧の数をカウントします。文字列を一文字ずつ読み込み、開き括弧が現れた場合はカウンターを増やし、閉じ括弧が現れた場合はカウンターを減らします。最終的にカウンターがゼロであれば括弧はバランスしています。以下にC++のコード例を示します:

#include <iostream>
using namespace std;
bool isBalanced(string s) {
   int counter = 0;
   for (char c : s) {
       if (c == '(') {
           counter++;
       } else if (c == ')') {
           counter--;
       }
// 他の括弧についても同様に処理を追加する
   }
   return counter == 0;
}
int main() {
   string s;
   cout << "Enter a string: ";
   cin >> s;
   if (isBalanced(s)) {
       cout << "Balanced" << endl;
   } else {
       cout << "Not balanced" << endl;
   }
   return 0;
}

これらのアルゴリズムは、文字列を一文字ずつ処理し、括弧の対応関係を確認するため効率的です。どちらの方法もO(N)の時間計算量を持ちます（Nは文字列の長さ）。

バランスした括弧の問題は、プログラミングの面接や競技プログラミングの問題としてよく出題されます。これらのアルゴリズムを理解し、応用できるようになると役立つでしょう。

以上、C++でのバランスした括弧の解決方法とコード例についてのブログ投稿でした。