ที่นี่เราจะมาดูวิธีรับคะแนนเท่ากันในวงเล็บ จุดเท่ากันคือดัชนี I เพื่อให้จำนวนวงเล็บเปิดก่อนหน้านั้นเท่ากับจำนวนวงเล็บปิดหลังจากนั้น สมมติว่าวงเล็บปีกกาเหมือน “(()))(()()())))” หากเราเห็นใกล้กว่านี้ เราก็จะได้
ดังนั้นจำนวนวงเล็บเปิดตั้งแต่ 0 ถึง 9 คือ 5 และจำนวนวงเล็บปิดตั้งแต่ 9 ถึง 14 ก็เป็น 5 ด้วย ดังนั้นนี่คือจุดเท่ากัน
เพื่อแก้ปัญหานี้ เราต้องทำตามขั้นตอนเหล่านี้ -
- จัดเก็บจำนวนวงเล็บเปิดปรากฏในสตริงจนถึงทุกดัชนี i
- เก็บจำนวนวงเล็บปิดที่ปรากฏในสตริงจนถึงแต่ละดัชนี I แต่ควรทำจากดัชนีสุดท้าย
- ตรวจสอบว่าดัชนีมีค่าเท่ากับวงเล็บเปิดและวงเล็บปิดหรือไม่
ตัวอย่าง
#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);
} ผลลัพธ์
Index of equal point: 9
