คะแนนของวงเล็บในภาษา C++

สมมติว่าเรามีวงเล็บสมดุล S เราต้องคำนวณคะแนนของสตริงตามกฎต่อไปนี้ -

• The () มีคะแนน 1
• AB มีคะแนน A + B โดยที่ A และ B เป็นสตริงที่สมดุลสองสตริง
• (A) มีคะแนน 2 * A โดยที่ A คือวงเล็บสมดุล

ดังนั้นหากอินพุตเป็นเหมือน “(()(()))” ผลลัพธ์จะเป็น 6

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ans :=0 กำหนดสแต็ก st
• สำหรับ i ในช่วง 0 ถึงขนาดของสตริง S
  • ถ้า S[i] เปิดวงเล็บ ให้ใส่ -1 ลงใน stack
  • อย่างอื่น
    • หากด้านบนของสแต็กเป็น -1 ให้ลบออกจากสแต็กแล้วแทรก 1 ลงในสแต็ก
    • อย่างอื่น
      • x :=0
      • ในขณะที่ด้านบนของ stack ไม่ใช่ -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