C ++中括号的分数

假设我们有一个平衡的括号字符串S，我们必须根据以下规则计算字符串的分数-

• ()的得分为1

• AB的得分为A + B，其中A和B是两个平衡的括号字符串。

• (A)的分数为2 * A，其中A是平衡的括号字符串。

因此，如果输入类似于“（()（()））”，则输出将为6。

为了解决这个问题，我们将遵循以下步骤-

• ans：= 0，定义堆栈st

• 对于i，范围为0至字符串S的大小

• 如果堆栈顶部为-1，则从堆栈中删除并将1插入堆栈

• 除此以外

• 由st增加x，从st删除

• x：= 0

• 而栈顶不是-1

• x：= x * 2

• 从st中删除，然后插入x

• 如果S [i]是开括号，则将-1插入堆栈

• 除此以外

• 当堆栈不为空时

• 通过st顶部增加ans，并删除top元素

• 返回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