Ở đây chúng ta sẽ xem cách lấy các điểm bằng nhau trong một chuỗi dấu ngoặc. Điểm bằng nhau là chỉ số I, sao cho số lượng dấu ngoặc mở trước nó bằng số lượng dấu ngoặc đóng sau nó. Giả sử một chuỗi ngoặc giống như “(())) (() () ())))”, nếu chúng ta nhìn gần hơn, chúng ta có thể nhận được
Vì vậy, số lượng dấu ngoặc mở từ 0 đến 9 là 5 và số lượng dấu ngoặc đóng từ 9 đến 14 cũng là 5, vì vậy đây là điểm bằng nhau.
Để giải quyết vấn đề này, chúng ta phải làm theo một số bước sau -
- Lưu trữ số lượng dấu ngoặc mở xuất hiện trong chuỗi lên đến mọi chỉ mục i
- Lưu trữ số lượng dấu ngoặc đóng xuất hiện trong chuỗi lên đến từng và mọi chỉ mục I nhưng việc này phải được thực hiện từ chỉ mục cuối cùng.
- Kiểm tra xem một chỉ mục có cùng giá trị mở và đóng ngoặc hay không.
Ví dụ
#include<iostream>
#include<cmath>
using namespace std;
int findEqualPoint(string str) {
int total_length = str.length();
int open[total_length+1] = {0}, close[total_length+1] = {0};
int index = -1;
open[0] = 0;
close[total_length] = 0;
if (str[0]=='(') //check whether first bracket is opening or not, if so mark open[1] = 1
open[1] = 1;
if (str[total_length-1] == ')') //check whether first bracket is closing or not, if so mark close[end] = 1
close[total_length-1] = 1;
for (int i = 1; i < total_length; i++) {
if ( str[i] == '(' )
open[i+1] = open[i] + 1;
else
open[i+1] = open[i];
}
for (int i = total_length-2; i >= 0; i--) {
if ( str[i] == ')' )
close[i] = close[i+1] + 1;
else
close[i] = close[i+1];
}
if (open[total_length] == 0)
return total_length;
if (close[0] == 0)
return 0;
for (int i=0; i<=total_length; i++)
if (open[i] == close[i])
index = i;
return index;
}
int main() {
string str = "(()))(()()())))";
cout << "Index of equal point: " << findEqualPoint(str);
} Đầu ra
Index of equal point: 9