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