C++での括弧のスコア

バランスの取れた括弧文字列Sがあるとすると、次のルールに基づいて文字列のスコアを計算する必要があります-

• （）のスコアは1です
• ABのスコアはA+Bです。ここで、AとBは2つのバランスの取れた括弧文字列です。
• （A）のスコアは2 * Aです。ここで、Aはバランスの取れた括弧文字列です。

したがって、入力が「（（）（（）））」のような場合、出力は6になります。

これを解決するには、次の手順に従います-

• ans：=0、スタックstを定義します
• 0から文字列Sのサイズまでの範囲のiの場合
  • S [i]が括弧を開いている場合は、スタックに-1を挿入します
  • それ以外の場合
    • スタックの最上位が-1の場合、スタックから削除して1をスタックに挿入します
    • それ以外の場合
      • x：=0
      • スタックの最上位が-1ではない場合
        • xをstずつ増やし、stから削除します
      • x：=x * 2
      • stから削除し、xを挿入します
• スタックが空でない間
  • stの先頭でansを増やし、一番上の要素を削除します
• 回答を返します。

理解を深めるために、次の実装を見てみましょう-

例

#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