Điểm của dấu ngoặc đơn trong C ++

Giả sử chúng ta có một chuỗi dấu ngoặc cân bằng S, chúng ta phải tính điểm của chuỗi dựa trên quy tắc sau -

• Dấu () có điểm 1
• AB có điểm A + B, trong đó A và B là hai chuỗi dấu ngoặc đơn cân đối.
• (A) có điểm 2 * A, trong đó A là một chuỗi dấu ngoặc đơn cân đối.

Vì vậy, nếu đầu vào là “(() (()))”, thì đầu ra sẽ là 6.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• ans:=0, xác định một ngăn xếp
• cho tôi trong phạm vi từ 0 đến kích thước của chuỗi S
  • nếu S [i] đang mở ngoặc, thì hãy chèn -1 vào ngăn xếp
  • nếu không thì
    • nếu đỉnh của ngăn xếp là -1, thì xóa khỏi ngăn xếp và chèn 1 vào ngăn xếp
    • nếu không thì
      • x:=0
      • trong khi đầu ngăn xếp không phải là -1
        • tăng x theo st, xóa khỏi st
      • x:=x * 2
      • xóa khỏi st và chèn x
• trong khi ngăn xếp không trống
  • tăng ans theo đầu và xóa phần tử trên cùng
• trả về ans.

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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("(()(()))"));
}

Đầu vào

"(()(()))"

Đầu ra

6