นับคู่ของลำดับวงเล็บเพื่อให้วงเล็บสมดุลใน C++

เราได้รับสตริงที่มีวงเล็บและภารกิจคือการคำนวณจำนวนคู่ของลำดับวงเล็บที่สามารถเกิดขึ้นได้เพื่อให้วงเล็บมีความสมดุล

วงเล็บมีความสมดุลเมื่อมีวงเล็บเปิดและปิดเท่ากัน วงเล็บที่ใช้ครั้งเดียวไม่สามารถถือเป็นคู่สำหรับการจัดคู่ได้

ป้อนข้อมูล − string paran[] ={ ")()())", "(", ")(", ")(", ")" }

ผลผลิต − จำนวนคู่ของลำดับวงเล็บที่วงเล็บมีความสมดุลคือ 1

คำอธิบาย − เราจะนำสตริงทุกชุดมาคำนวณการนับให้ดียิ่งขึ้น ให้นำองค์ประกอบแรกเป็น “)()())” ซึ่งมี 4 วงเล็บปิดและ 2 วงเล็บเปิด ดังนั้นเราจะมองหาองค์ประกอบถัดไปในสตริงที่มีวงเล็บปิด 2 อันเพื่อสร้างลำดับวงเล็บที่สมดุลซึ่งไม่ใช่ มีอยู่ในสตริงดังนั้นเราจะทิ้งมันและไปต่อไป ดังนั้นคู่ที่ถูกต้องซึ่งมีวงเล็บเปิดและปิดเท่ากันอยู่ที่ (2, 5) ดังนั้นการนับคือ 1

ป้อนข้อมูล − string paran[] ={ ")()())", "((", "(", ")(", ")(", ")"}

ผลผลิต − จำนวนคู่ของลำดับวงเล็บที่วงเล็บมีความสมดุลคือ 1

คำอธิบาย − คู่วงเล็บสมดุลที่ถูกต้องอยู่ที่ (1, 2) และ (3, 6) ดังนั้นการนับคือ 2

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

• ป้อนสตริงและคำนวณความยาวของสตริงโดยใช้ฟังก์ชัน length() และส่งข้อมูลไปยังฟังก์ชันเพื่อการประมวลผลต่อไป

• นับตัวแปรชั่วคราวเพื่อเก็บวงเล็บคู่ที่ถูกต้อง และสร้างตัวแปร um_1 และ um_2 ประเภท unordered_map

• เริ่มการวนซ้ำ FOR จาก 0 จนถึงขนาดของสตริง

• ภายในลูป ให้ตั้งค่า str เป็น paran[i] เช่น องค์ประกอบแรกของวงเล็บ และคำนวณความยาวของสตริงอีกครั้ง

• ใช้ตัวแปรชั่วคราวเป็นค่าแรกและค่าสุดท้ายและกำหนดค่าเริ่มต้นด้วย 0

• เริ่มลูปอื่น FOR จาก j ถึง 0 จนถึงความยาวของสตริง

• ภายในลูป ให้ตรวจสอบ IF str[j] ='(' จากนั้นให้เพิ่มค่าแรกขึ้น 1 ค่า ELSE ตรวจสอบ IF ก่อน =1 จากนั้นให้ลดค่าค่าแรกลง 1 ค่า ELSE เพิ่มค่าสุดท้ายทีละ 1

• ตอนนี้ให้ตรวจสอบว่า IF อันดับแรกคือ 1 และสุดท้ายคือ 0 จากนั้นตั้งค่า um_1[ก่อน]++ และตรวจสอบว่า IF สุดท้ายคือ 1 และอันดับแรกคือ 0 จากนั้นตั้งค่า um_2[lst]++ และ IF ก่อนเป็น 0 และสุดท้ายเป็น 0 ด้วย จากนั้นให้เพิ่มจำนวน โดย 1.

• ตั้งนับเป็นจำนวน / 2

• เริ่มวนซ้ำจาก 0 ถึง um_1 และตั้งค่าให้เป็นค่าต่ำสุดจาก um_1.second และ um_2.first

• คืนจำนวน

• พิมพ์ผลลัพธ์

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
int parentheses(string paran[], int size){
   int count = 0;
   unordered_map<int, int> um_1, um_2;
   for (int i = 0; i < size; i++){
      string str = paran[i];
      int len = str.length();
      int first = 0;
      int last = 0;
      for (int j = 0; j < len; j++){
         if (str[j] == '('){
            first++;
         }
         else{
            if (first==1){
               first--;
            }
            else{
               last++;
            }
         }
      }
      if(first==1 && last!=1){
         um_1[first]++;
      }
      if (last==1 && first!=1){
         um_2[last]++;
      }
      if(first!=1 && last!=1){
         count++;
      }
   }
   count = count / 2;
   for (auto it : um_1){
      count += min(it.second, um_2[it.first]);
   }
   return count;
}
int main(){
   string paran[] = { ")()())", "(", ")(", ")(", ")"};
   int size = sizeof(paran) / sizeof(paran[0]);
   cout<<"Count of pairs of parentheses sequences such that parentheses are balanced are:
"<<parentheses(paran, size);
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

Count of pairs of parentheses sequences such that parentheses are balanced are: 1