C++で有効な括弧列にするために追加すべき括弧の最小数

問題文

開き括弧「(」と閉じ括弧「)」のみで構成された文字列が与えられます。この文字列を有効な括弧列(すべての括弧が正しく対応している状態)にするために、追加が必要な括弧の最小個数を求めてください。

例

str = "((()" の場合、末尾に閉じ括弧「))」を2つ追加して "((()))" とすれば有効な括弧列になります。したがって答えは 2 です。

アルゴリズム

単純に「開き括弧の総数と閉じ括弧の総数の差の絶対値」を答えとする方法は、")(" のように閉じ括弧が開き括弧より先に現れるケースで誤った結果(0)を返してしまうため注意が必要です。正しく求めるには、文字列を先頭から走査しながら対応する相手を持たない括弧の数を数えます。

1. 未対応の開き括弧の数 open と、未対応の閉じ括弧の数 close を 0 で初期化します。
2. 文字列を左から右へ1文字ずつ走査します。
3. 「(」を見つけたら open を1増やします。
4. 「)」を見つけたら、open > 0 なら対応する開き括弧とマッチするので open を1減らし、open == 0 なら close を1増やします。
5. 走査終了時の open + close が求める答えです。

C++実装例

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

int requiredParentheses(const string& str) {
    int open = 0, close = 0;
    for (char c : str) {
        if (c == '(') {
            ++open;
        } else if (c == ')') {
            if (open > 0) {
                --open;   // 対応する開き括弧とマッチ
            } else {
                ++close;  // マッチする開き括弧がない
            }
        }
    }
    return open + close;
}

int main() {
    string str = "((()";
    cout << "Required parentheses = " << requiredParentheses(str) << endl;
    return 0;
}

このプログラムをコンパイルして実行すると、次の出力が得られます。

Required parentheses = 2

計算量

• 時間計算量: O(n) — 文字列を1回走査するだけです。
• 空間計算量: O(1) — カウンタ変数2つのみを使用します。