C ++中括号的分数

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个平衡的括号字符串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

    以上是 C ++中括号的分数 的全部内容， 来源链接： utcz.com/z/343394.html

    回到顶部