C++で余分な括弧を削除して文字列のバランスを取る方法

文字列とは、文字の配列のことです。この問題では、開き括弧と閉じ括弧を含む文字列が与えられ、余分な括弧を削除することで文字列のバランスを取ることを目標とします。

具体的な例を見てみましょう。

入力 : ")Tutor)ials(p(oin)t(...)"
出力 : "Tutorials(p(oin)t(...))"

入力文字列には、対応する開き括弧を持たない閉じ括弧「)」が含まれています。このような余分な括弧を取り除くことで、括弧の対応が正しいバランスの取れた文字列を作成します。

解決のアプローチ

この問題を解くには、文字列を先頭から順に走査し、括弧の対応関係をチェックします。開き括弧と閉じ括弧が正しく対応している場合はそのまま出力し、対応しない余分な閉じ括弧は削除します。また、走査の終了後に開き括弧が余っている場合は、必要な数だけ閉じ括弧を末尾に追加します。

アルゴリズム

ステップ 1 : 文字列を左から右へ走査する。
ステップ 2 : 開き括弧「(」が出現した場合は出力し、カウントを 1 増やす。
ステップ 3 : 閉じ括弧「)」が出現した場合は、カウントが 0 より大きいときのみ出力し、カウントを 1 減らす。
ステップ 4 : 括弧以外の文字はすべてそのまま出力する。
ステップ 5 : 最後に、カウントが 0 になるまで閉じ括弧「)」を末尾に追加する(追加するごとにカウントを減らす)。

サンプルコード

#include<iostream>
#include<string.h>
using namespace std;
void balancedbrackets(string str){
    int count = 0, i;
    int n = str.length();
    for (i = 0; i < n; i++) {
        if (str[i] == '(') {
            cout << str[i];
            count++;
        }
        else if (str[i] == ')' && count != 0) {
            cout << str[i];
            count--;
        }
        else if (str[i] != ')')
            cout << str[i];
    }
    if (count != 0)
        for (i = 0; i < count; i++)
            cout << ")";
}
int main() {
    string str = ")Tutor)ials(p(oin)t(...)";
    cout<<"Original string : "<<str;
    cout<<"\nBalanced string : ";
    balancedbrackets(str);
    return 0;
}

実行結果

Original string : )Tutor)ials(p(oin)t(...)
Balanced string : Tutorials(p(oin)t(...))

コードの解説

このプログラムでは、変数 count を使って現在開いている括弧の数を追跡しています。

• 開き括弧「(」は必ず出力し、カウントを増やします。
• 閉じ括弧「)」は、対応する開き括弧が存在する(カウントが 0 でない)場合にのみ出力します。これにより、余分な閉じ括弧が自動的に除去されます。
• 走査が終わった時点でカウントが残っている場合は、開き括弧が閉じられていないことを意味するため、必要な数だけ閉じ括弧を末尾に追加します。

このアルゴリズムの計算量は O(n) で、文字列の長さに比例した一度の走査で処理が完了するため、非常に効率的です。