C++で括弧の番号（ブラケット番号）を出力する方法

問題概要

この問題では、括弧を含む式が与えられ、その括弧の番号列を出力することが求められます。まず具体例を見て、問題の内容をしっかり理解しましょう。

例：

入力 : ((()())())
出力 : 1233442551

解説 ― この式には5組の括弧ペアが含まれており、それぞれの括弧が出現した順序に従って番号を出力しています。

問題の内容が把握できたところで、次に解決策を考えていきましょう。

解法のアプローチ

この問題を効率的に解くには、スタックというデータ構造を活用します。具体的には、左括弧「(」の個数を数えるための変数を1つ用意し、スタックで対応する右括弧「)」の情報を管理します。左括弧が出現するたびに通し番号を割り振ってスタックにプッシュし、右括弧が出現したタイミングでスタックからポップすることで、対応するペアの番号を出力できます。

アルゴリズム

ステップ1 : leftBrackets = 1 で初期化し、空のスタック rightBrackets を用意する。
ステップ2 : 変数 i を 0 から n-1 まで動かしながら式を走査する。
ステップ3 : expression[i] == '(' の場合（左括弧が出現した場合）：
  ステップ3.1 : leftBracket の値を出力する。
  ステップ3.2 : leftBracket の値をスタックにプッシュする。
  ステップ3.3 : leftBracket をインクリメントする。
ステップ4 : expression[i] == ')' の場合（右括弧が出現した場合）：
  ステップ4.1 : スタックの先頭要素を出力する。
  ステップ4.2 : スタックの先頭要素をポップする。
ステップ5 : 終了する。

C++での実装例

それでは、上記のアルゴリズムを実装したC++プログラムを作成してみましょう。

#include <bits/stdc++.h>
using namespace std;
void bracketCount(string expression, int n){
    int leftBracket = 1;
    stack<int> rightBracket;
    for (int i = 0; i < n; i++) {
        if (expression[i] == '(') {
            cout<<leftBracket<<" ";
            rightBracket.push(leftBracket);
            leftBracket++;
        }
        else if(expression[i] == ')') {
            cout<<rightBracket.top() << " ";
            rightBracket.pop();
        }
    }
}
int main(){
    string expression = "()((())()())";
    int n = expression.size();
    bracketCount(expression, n);
    return 0;
}

出力結果

1 1 2 3 4 4 3 5 5 6 6 2

コードのポイント

このアルゴリズムの計算量は O(n) です。式全体を一度だけ走査し、各括弧に対して出力・プッシュ・ポップといった定数時間の処理を行うだけで済むため、非常に効率的な手法と言えます。また、スタックの「後入れ先出し（LIFO）」という性質により、ネストされた括弧の対応関係も正確に追跡できる点が大きな特徴です。