C++で文字列から無効な括弧を削除し、有効な括弧列をすべて出力する方法

括弧を含む文字列が与えられたとき、無効な括弧を取り除くことで得られる、考えられるすべての有効な括弧列を出力する問題を考えてみましょう。まずは具体例から見ていきます。

入力 : str = "()())()"
出力 : ()()() (())()
2つの解が存在します
"()()()" と "(())()"

入力 : str = "(v)())()"
出力 : (v)()() (v())()

この問題では、バックトラッキングの考え方を用いることで、条件を満たすすべての有効な文字列を出力できます。

解決のためのアプローチ

このアプローチでは、BFS(幅優先探索)を使って、開き括弧と閉じ括弧を1つずつ順番に削除していきます。生成された各文字列について、それが有効な括弧列かどうかを判定し、有効であれば出力します。

サンプルコード

 
#include <bits/stdc++.h>
using namespace std;
bool isParenthesis(char c){
    return ((c == '(') || (c == ')'));
}
bool validString(string str){
    // cout << str << " ";
    int cnt = 0;
    for (int i = 0; i < str.length(); i++){
        if (str[i] == '(')
           cnt++;
        else if (str[i] == ')')
           cnt--;
        if (cnt < 0)
           return false;
    }
    // cout << str << " ";
    return (cnt == 0);
}
void validParenthesesSequences(string str){
    if (str.empty())
        return ;
    set<string> visit; // 一度チェックした文字列はvisitに入れておき、
                      // 同じ文字列を再度処理しないようにする
    queue<string> q; // BFSを行うためのキュー
    string temp;
    bool level;
    // 入力文字列を起点ノードとしてキューに追加
    q.push(str);
    visit.insert(str);
    while (!q.empty()){
        str = q.front(); q.pop();
        if (validString(str)){
        //    cout << "s";
            cout << str << "\n"; // 有効な文字列を出力
            level = true; // 同一レベルで解が見つかったため、そこからのBFS展開は不要
        }
        if (level)
            continue;
        for (int i = 0; i < str.length(); i++){
            if (!isParenthesis(str[i])) // 括弧以外の文字は削除対象外
                continue;
            temp = str.substr(0, i) + str.substr(i + 1); // 括弧を1つずつ削除した文字列を生成
            if (visit.find(temp) == visit.end()) { // 未チェックの文字列のみキューに追加
                q.push(temp);
                visit.insert(temp);
            }
        }
    }
}
int main(){
    string s1;
    s1 = "(v)())()";
    cout << "Input : " << s1 << "\n";
    cout << "Output : ";
    validParenthesesSequences(s1);
    return 0;
}

実行結果

Input : (v)())()
Output : (v())()

コードの解説

上記のアプローチでは、括弧を1つずつ順番に削除しながら探索を進めます。その際、すでに確認済みの文字列をsetで管理しておくことで、同じ文字列を二度チェックする無駄を省いています。こうして生成されたすべての候補の中から有効な括弧列が見つかれば、それらをすべて出力します。これがこのプログラムの一連の流れです。

まとめ

本記事では、「無効な括弧の削除(Remove Invalid Parentheses)」という問題を解説しました。BFSを用いた解法の全体像と、それを実装したC++プログラムを学びました。なお、同じロジックはC、Java、Pythonなど他のプログラミング言語でも実装可能です。皆さんの学習の参考になれば幸いです。