C++で式に重複した括弧が含まれているかどうかを判定する方法

式 exp が与えられたとき、その式に重複した括弧が含まれているかどうかを確認する問題を考えてみましょう。ある部分式が2組以上の括弧で囲まれている場合、その式は重複した括弧を持つことになります。

例えば、次のような式を見てください。

(5+((7−3)))

この例では、部分式 (7 − 3) が2組の括弧で囲まれているため、重複した括弧が存在します。

解決アプローチ：スタックを使った判定

この問題は、スタックを使うことで効率的に解くことができます。アルゴリズムの手順は以下の通りです。

1. 式内の各文字を先頭から順に走査します。
2. 文字が開き括弧「(」、演算子、またはオペランドである場合は、スタックにプッシュします。
3. 文字が閉じ括弧「)」である場合は、対応する開き括弧が見つかるまでスタックから文字をポップし続けます。
4. このとき、開き括弧と閉じ括弧の間に存在する文字の数をカウントします。
5. カウントが 1 未満であれば、その括弧の間に有効な式が存在しないことになり、重複した括弧が見つかったと判断できます。

すべての文字を処理しても重複が検出されなければ、式に重複した括弧は含まれていないことになります。

C++での実装例

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

bool hasDuplicateParentheses(string str) {
    stack<char> stk;
    for (int i = 0; i < str.length(); i++) {
        char ch = str[i];
        if (ch == ')') {
            char top = stk.top();
            stk.pop();
            int count = 0;
            // 開き括弧が見つかるまでポップしながら文字数をカウント
            while (top != '(') {
                count++;
                top = stk.top();
                stk.pop();
            }
            // 括弧の間に文字がなければ重複した括弧
            if (count < 1) {
                return true;
            }
        }
        else {
            stk.push(ch);
        }
    }
    return false;
}

int main() {
    string str = "(5+((7-3)))";
    if (hasDuplicateParentheses(str))
        cout << "Duplicate parentheses has Found";
    else
        cout << "No Duplicates parentheses has Found";
}

実行結果

Duplicate parentheses has Found

計算量について

このアルゴリズムの時間計算量は O(n)、空間計算量も O(n) です（n は式の長さ）。各文字は最大でも一度プッシュされ、一度ポップされるだけなので、非常に効率的な手法と言えます。