C++ 中括号的分值

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

  • () 的分值为 1
  • AB 的分值为 A + B，其中 A 和 B 是两个平衡的括号字符串。
  • (A) 的分值为 2 * A，其中 A 是一个平衡的括号字符串。

因此，如果输入类似于“(()(()))”，那么输出将为 6。

为了解决此问题，我们将按照以下步骤操作 -

  • ans := 0，定义一个栈 st
  • 对于 i 的范围从 0 到字符串 S 的长度
    • 如果 S[i] 是左括号，那么将 -1 插入栈
    • 否则
      • 如果栈顶为 -1，那么从栈中删除并插入 1
      • 否则
        • x := 0
        • 当栈顶不为 -1 时
          • 将 x 增加 st 的值，从 st 中删除
        • x := x * 2
        • 从 st 中删除，并插入 x
  • 当栈不为空时
    • 将 ans 增加 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

更新于： 05-05-2020

295 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始使用
广告