C++でバランスの取れた括弧文字列のスコアを計算する方法

問題概要

バランスの取れた括弧文字列 S が与えられたとき、以下のルールに基づいてその文字列のスコアを計算することを考えます。

• () のスコアは 1
• AB のスコアは A + B(A と B はそれぞれバランスの取れた括弧文字列)
• (A) のスコアは 2 × A(A はバランスの取れた括弧文字列)

たとえば、入力が「(()(()))」の場合、出力は 6 になります。

アルゴリズム(スタックを利用した解法)

この問題はスタックを使うことで効率的に解くことができます。解法の手順は以下の通りです。

1. ans := 0 と初期化し、整数型のスタック st を用意する
2. i を 0 から文字列 S のサイズまで繰り返す
   • S[i] が開き括弧「(」の場合:-1 をスタックにプッシュする
   • それ以外の場合:
     • スタックの先頭が -1 なら、それをポップして 1 をプッシュする
     • それ以外の場合:
       • x := 0 とする
       • スタックの先頭が -1 でない間、x に先頭の値を加算しながらポップを続ける
       • x を 2 倍する
       • -1 をポップし、x をプッシュする
3. スタックが空になるまで、ans に先頭の値を加算しながらポップする
4. ans を返す

考え方のポイント

ここでは -1 を「開き括弧」の目印として扱っています。閉じ括弧「)」に遭遇したとき、スタックの先頭が -1 であればそれは「()」というペアなのでスコア 1 を記録します。一方、先頭にすでに数値が積まれている場合は、内側のスコアをすべて合計して 2 倍することで「(A)」のルールを表現できます。最後にスタックに残った値をすべて足し合わせるのが答えになります。

C++による実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int scoreOfParentheses(string S) {
        int ans = 0;
        stack <int> st;
        for(int i = 0; i < S.size(); i+=1){
            if(S[i] == '('){
                st.push(-1);
            }else{
                if(st.top() == -1){
                    st.pop();
                    st.push(1);
                }else{
                    int x = 0;
                    while(st.top() != -1){
                        x += st.top();
                        st.pop();
                    }
                    x *= 2;
                    st.pop();
                    st.push(x);
                }
            }
        }
        while(!st.empty()){
            ans += st.top();
            st.pop();
        }
        return ans;
    }
};
main(){
    Solution ob;
    cout << (ob.scoreOfParentheses("(()(()))"));
}

入力

"(()(()))"

出力

6

計算量

このアルゴリズムの時間計算量は O(N)(N は文字列の長さ)、空間計算量も O(N) です。各文字を一度だけ走査し、スタックへのプッシュ・ポップはいずれも定数時間で行えるため、非常に効率的な解法となっています。