C++で置換によりバランスの取れた括弧式を判定する方法

バランスの取れた括弧式とは？

バランスの取れた括弧式とは、すべての種類の括弧が正しい順序で対になっている式のことです。つまり、開き括弧「{」「[」「(」の一つひとつに対して、適切な順序で対応する閉じ括弧「}」「]」「)」が存在する状態を指します。

具体例を見ながら、この概念をより深く理解しましょう。

• 入力式： {([][]{})({}[]{})}
• 出力： バランスが取れている
• 説明： すべての開き括弧に対して、正しい順序で閉じ括弧が対応しています。開き括弧と閉じ括弧の間に挟まれた括弧も、それぞれ正しくペアになっています。

• 出力： バランスが取れていない
• 説明： 順序が崩れた括弧のペアが存在するため、式全体がバランスしていない状態になっています。

「置換によるバランス式」問題とは

本記事で扱うのは「置換によるバランス式」と呼ばれる問題です。括弧「{」「}」「[」「]」「(」「)」で構成された文字列が与えられますが、一部の位置では括弧が欠落しており、代わりに「*」が置かれています。この「*」を適切な括弧に置き換えることで、与えられた式が有効な（バランスの取れた）式になるかどうかを判定する必要があります。

例1

• 入力： exp = "{[*(*)]}"
• 出力： 式はバランスを取ることができる
• 説明： 置換が必要な記号は2つです。「*」を適切な括弧に置き換えると {[(())]} となり、有効な式になります。

例2

• 入力： exp = "[(*){}{{}}]"
• 出力： 式はバランスを取ることができない
• 説明： 置換が必要な記号は1つですが、「*」をどの括弧に置き換えても、式全体をバランスさせることはできません。

解決策：スタックを活用したアプローチ

問題の内容をしっかりと理解できたところで、解決策を考えていきましょう。与えられた括弧式がバランスしているかどうかを確認するには、スタックというデータ構造を利用するのが効果的です。

このタスクを遂行するために行う処理は以下の通りです。

1. 文字列式の各要素を走査し、以下の処理を実行します。
2. 開き括弧「{」「[」「(」に遭遇した場合は、その要素をスタックにプッシュします。
3. 閉じ括弧「}」「]」「)」に遭遇した場合は、スタックの先頭要素をポップし、それが遭遇した閉じ括弧に対応する開き括弧であるかを確認します。
   • 両者の括弧が一致していれば、次の要素の処理へ進みます。
   • 一致していなければ、その式はバランスが取れていないと判定します。
4. 「*」に遭遇した場合（開き括弧にも閉じ括弧にもなり得る）は、以下のように処理します。
   • まず開き括弧として扱い、スタックにプッシュします。その後、再帰呼び出しによって次の要素以降に対応する閉じ括弧が見つかるかを調べます。結果がfalseであれば、次の手順に進みます。
   • 続いて閉じ括弧として扱います。この場合、スタックの先頭要素と一致する必要があり、一致すれば先頭要素をポップします。
   • 「*」を閉じ括弧としても対応する開き括弧が見つからなければ、バランスが取れていないと返します。
5. 最終的な結果に基づいてメッセージを出力します。

C++での実装例

それでは、上記の解決策をもとに実際のプログラムを作成してみましょう。

#include <bits/stdc++.h>
using namespace std;

int isMatching(char a, char b){
    if ((a == '{' && b == '}') || (a == '[' && b == ']') ||
        (a == '(' && b == ')') || a == '*')
        return 1;
    return 0;
}

int isBalancedexpression(string s, stack<char> ele, int ind){
    if (ind == s.length())
        return ele.empty();
    char topEle;
    int res;
    if (s[ind] == '{' || s[ind] == '(' || s[ind] == '[') {
        ele.push(s[ind]);
        return isBalancedexpression(s, ele, ind + 1);
    }
    else if (s[ind] == '}' || s[ind] == ')' || s[ind] == ']') {
        if (ele.empty())
            return 0;
        topEle = ele.top();
        ele.pop();
        if (!isMatching(topEle, s[ind]))
            return 0;
        return isBalancedexpression(s, ele, ind + 1);
    }
    else if (s[ind] == '*') {
        stack<char> tmp = ele;
        tmp.push(s[ind]);
        res = isBalancedexpression(s, tmp, ind + 1);
        if (res)
            return 1;
        if (ele.empty())
            return 0;
        ele.pop();
        return isBalancedexpression(s, ele, ind + 1);
    }
}

int main(){
    string s = "{[*(*)]}";
    stack<char> ele;
    if (isBalancedexpression(s, ele, 0))
        cout << "Balanced";
    else
        cout << "Not Balanced";
    return 0;
}

出力結果

Balanced

まとめ

このように、スタックと再帰を組み合わせることで、「*」を含む括弧式が有効な式になり得るかどうかを効率的に判定できます。ただし、「*」が出現するたびに「開き括弧として扱う場合」と「閉じ括弧として扱う場合」の2通りの探索が発生するため、計算量は「*」の個数をkとすると最大でO(2^k)程度に増大する点には注意が必要です。入力文字列が長くなる場合は、メモ化や枝刈りなどの工夫を加えることで実用性を高めることができます。