แนวคิด
สำหรับสตริงที่กำหนดซึ่งมีอักขระ '(', ')', '{', '}', '[' และ ']' ภารกิจคือการค้นหาว่าวงเล็บเหลี่ยมมีความสมดุลหรือไม่
วงเล็บจะถูกแสดงว่าสมดุลถ้า −
-
เราปิดวงเล็บเปิดต้องปิดด้วยวงเล็บประเภทเดียวกัน
-
เราปิดวงเล็บเปิดตามลำดับที่ถูกต้องอีกครั้ง
ป้อนข้อมูล − str =“(()){}”
ผลผลิต - ใช่
ป้อนข้อมูล − str =“))(([][”
ผลผลิต − ไม่
วิธีการ
-
กำหนดตัวแปร a และ b สองตัวเพื่อติดตามวงเล็บสองอันที่จะเปรียบเทียบ
-
ควรรักษาการนับที่มีค่าเพิ่มขึ้นเมื่อพบวงเล็บเปิดและลดลงเมื่อพบวงเล็บปิด
-
กำหนด b =a, a =a + 1 และ count=count+1 เมื่อพบวงเล็บเปิด
-
ในขณะที่พบวงเล็บปิด นับลดจำนวนและเปรียบเทียบวงเล็บที่ i และ j
-
หากพบว่าวงเล็บที่ a และ b ตรงกัน ให้แทนที่ '#' ในสตริงที่ตำแหน่ง th และ b a เพิ่มขึ้นและ b จะลดลงจนกว่าจะพบค่าที่ไม่ใช่ '#' หรือ b ≥ 0
-
หากพบว่าวงเล็บที่ a และ b ไม่ตรงกัน ให้คืนค่าเท็จ
-
-
หากนับ !=0 ให้คืนค่าเท็จ
ตัวอย่าง
// C++ implementation of the approach
#include <iostream>
using namespace std;
bool helperFunc(int& count1, string& s1, int& i1, int& j1, char tocom1){
count1--;
if (j1 > -1 && s1[j1] == tocom1) {
s1[i1] = '#';
s1[j1] = '#';
while (j1 >= 0 && s1[j1] == '#')
j1--;
i1++;
return 1;
}
else
return 0;
}
bool isValid(string s1){
if (s1.length() == 0)
return true;
else {
int i1 = 0;
int count1 = 0;
int j1 = -1;
bool result1;
while (i1 < s1.length()) {
switch (s1[i1]) {
case '}':
result1 = helperFunc(count1, s1, i1, j1, '{');
if (result1 == 0) {
return false;
}
break;
case ')':
result1 = helperFunc(count1, s1, i1, j1, '(');
if (result1 == 0) {
return false;
}
break;
case ']':
result1 = helperFunc(count1, s1, i1, j1, '[');
if (result1 == 0) {
return false;
}
break;
default:
j1 = i1;
i1++;
count1++;
}
}
if (count1 != 0)
return false;
return true;
}
}
// Driver code
int main(){
string str1 = "[[]][]()";
if (isValid(str1))
cout << "Yes";
else
cout << "No";
return 0;
} ผลลัพธ์
Yes
