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 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始使用
廣告