พิมพ์หมายเลขวงเล็บในภาษา C++

ในปัญหานี้ เราได้รับนิพจน์ และเราต้องพิมพ์ลำดับเลขวงเล็บ มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากันดีกว่า

ตัวอย่าง

Input : ((()())())
Output : 1233442551

คำอธิบาย − ที่นี่เราพบคู่วงเล็บ 5 คู่ และเราได้พิมพ์ตามลำดับของ [ การเกิดขึ้น

เนื่องจากเราทราบปัญหาแล้ว มาสร้างวิธีแก้ปัญหานี้กัน

การแก้ปัญหานี้ต้องใช้โครงสร้างข้อมูลแบบสแตก เราจะใช้ตัวแปรหนึ่งตัวที่คอยนับจำนวนวงเล็บซ้าย และกองซ้อนติดตามวงเล็บเหลี่ยมขวา เราจะนับวงเล็บด้านซ้ายและดันเข้าไปในสแต็กและป๊อปอัปเมื่อพบวงเล็บด้านขวา

อัลกอริทึม

Step 1 : Initialise leftBrackets = 1. stack rightBrackets, empty.
Step 2 : traverse the expression using variable i = 0 to n-1.
Step 3 : if expression[i] == ‘(’ i.e. left bracket is encountered. Then,
   Step 3.1 : PRINT ‘leftBracket ‘.
   Step 3.2 : push the value of leftBracket in stack.
   Step 3.3 : leftBracket++.
Step 4 : if expression[i] == ‘)’ i.e. right bracket is encountered. Then,
   Step 4.1 : PRINT top of stack.
   Step 4.2 : pop top element of the stack.
Step 5 : EXIT.

ตัวอย่าง

ตอนนี้ มาสร้างการเขียนโปรแกรมเพื่อแสดงการใช้งานอัลกอริธึมข้างต้นกัน

#include <bits/stdc++.h>
using namespace std;
void bracketCount(string expression, int n){
   int leftBracket = 1;
   stack<int> rightBracket;
   for (int i = 0; i < n; i++) {
      if (expression[i] == '(') {
         cout<<leftBracket<<" ";
         rightBracket.push(leftBracket);
         leftBracket++;
      }
      else if(expression[i] == ')') {
         cout<<rightBracket.top() << " ";
         rightBracket.pop();
      }
   }
}
int main(){
   string expression = "()((())()())";
   int n = expression.size();
   bracketCount(expression, n);
   return 0;
}

ผลลัพธ์

1 1 2 3 4 4 3 5 5 6 6 2