C++で指定された開き括弧に対応する閉じ括弧のインデックスを検索する方法

括弧を含む数式を扱う際、特定の開き括弧「(」に対応する閉じ括弧「)」の位置を求めたいケースがあります。例えば、次のような式を考えてみましょう。

(25*6+(88-32+(50/10)+20))

この式において、インデックス6の位置にある開き括弧に対応する閉じ括弧は、インデックス23の位置に存在します。

スタックを使った解法の考え方

この問題は、スタック（Stack）というデータ構造を使うことで効率的に解決できます。アルゴリズムの流れは以下の通りです。

1. 指定されたインデックスから式の走査を開始します。
2. 開き括弧「(」を見つけるたびに、スタックにプッシュします。
3. 閉じ括弧「)」を見つけたら、スタックから要素をポップします。
4. ポップ後にスタックが空になった時点のインデックスが、求める閉じ括弧の位置です。

この方法により、括弧のネスト（入れ子）構造を正確に追跡しながら、対応する閉じ括弧を特定できます。

C++による実装例

#include<iostream>
#include<stack>
using namespace std;

void getEndingBracketIndex(string exp, int index){
    int i;
    // 指定位置が開き括弧でない場合はエラー扱い
    if(exp[index]!='('){
        cout << exp << "Closing bracket of parentheses started at " << index << " present at index -1\n";
        return;
    }
    stack <int> stk;
    for(i = index; i < exp.length(); i++){
        if(exp[i] == '(')
            stk.push(exp[i]);
        else if(exp[i] == ')'){
            stk.pop();
            // スタックが空になったら対応する閉じ括弧を発見
            if(stk.empty()){
                cout << exp << ", Closing bracket of parentheses started at " << index << " present at index " << i << "";
                return;
            }
        }
    }
    // 対応する閉じ括弧が見つからなかった場合
    cout << exp << ", Closing bracket of parentheses started at " << index << " present at index -1";
}

int main() {
    getEndingBracketIndex("(25*6+(88-32+(50/10)+20))", 6);
}

実行結果

(25*6+(88-32+(50/10)+20)), Closing bracket of parentheses started at 6 present at index 23

コードのポイント

• 入力チェック： 指定されたインデックスの文字が開き括弧「(」でない場合は、結果として「-1」を出力して終了します。
• ネスト対応： スタックの深さを利用することで、括弧が何重に入れ子になっていても正しく対応関係を判定できます。
• 計算量： 式の長さを n とすると、時間計算量は O(n)、空間計算量は O(n) となります。

このアルゴリズムは、構文解析や数式エディタ、コードエディタの括弧ハイライト機能など、さまざまな場面で応用できる基本的なテクニックです。