In số trong ngoặc vuông trong C ++

Trong bài toán này, chúng ta có biểu thức. Và chúng ta phải in dãy số trong ngoặc. Hãy xem một ví dụ để hiểu rõ vấn đề hơn.

Ví dụ,

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

Giải thích - Ở đây, chúng tôi đã gặp 5 cặp dấu ngoặc và chúng tôi đã in chúng theo chuỗi [lần xuất hiện của chúng.

Bây giờ chúng ta đã biết về vấn đề này, chúng ta hãy tạo ra một giải pháp cho giải pháp này.

Giải pháp cho vấn đề này yêu cầu cấu trúc dữ liệu ngăn xếp. Chúng tôi sẽ sử dụng một biến giữ số lượng các dấu ngoặc vuông bên trái và ngăn xếp theo dõi các dấu ngoặc vuông bên phải. Chúng tôi sẽ đếm các dấu ngoặc vuông bên trái và đẩy chúng vào ngăn xếp và bật lên khi gặp dấu ngoặc vuông bên phải.

Thuật toán

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.

Ví dụ

Bây giờ, hãy tạo chương trình để minh họa việc triển khai thuật toán trên.

#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;
}

Đầu ra

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